PreviousNext
Coding/Bits and math

Modular multiplicative inverse

Write codeHard30 min

Your task

Given integers a and m (1 <= a < m <= 10^9), return the modular multiplicative inverse of a modulo m, the integer x in [0, m) such that (a * x) % m == 1. If no inverse exists (because a and m are not coprime), return -1. Do not assume m is prime.

Examples

mod_inverse(a: int, m: int) -> int
Example 1
Inputmod_inverse(3, 11)
Output4