Modular Inverse - Classic Problems | Repovive

CLS25. Modular Inverse

1s256 MB

Given integers $a$ and $m$ (where $m$ is a prime number), find the modular multiplicative inverse of $a$ modulo $m$ .

The modular inverse of $a$ modulo $m$ is an integer $x$ such that: $a \cdot x \equiv 1 \pmod{m}$

When $m$ is prime and $a$ is not divisible by $m$ , use Fermat's Little Theorem: $a^{-1} \equiv a^{m-2} \pmod{m}$

$a \quad m$

$a^{-1} \mod m$

Input

3 7

Explanation

For this input, the required output is 5.

Output

Input

2 5

Explanation

For this input, the required output is 3.

Output

Input

4 11

Explanation

For this input, the required output is 3.

Output

1s256 MB

Given integers $a$ and $m$ (where $m$ is a prime number), find the modular multiplicative inverse of $a$ modulo $m$ .

The modular inverse of $a$ modulo $m$ is an integer $x$ such that: $a \cdot x \equiv 1 \pmod{m}$

When $m$ is prime and $a$ is not divisible by $m$ , use Fermat's Little Theorem: $a^{-1} \equiv a^{m-2} \pmod{m}$

$a \quad m$

$a^{-1} \mod m$

Input

3 7

Explanation

For this input, the required output is 5.

Output

Input

2 5

Explanation

For this input, the required output is 3.

Output

Input

4 11

Explanation

For this input, the required output is 3.

Output