Modular Inverse

Compute the modular inverse of a number modulo m when it exists.

modular-arithmetic euclid math

Write a function `mod_inverse(a, m)` that returns the modular inverse of `a` modulo `m`. The modular inverse is an integer `x` in the range `0 < x < m` such that `(a * x) % m == 1`. If no such integer exists, return `-1`.

Assumptions:
- `m` is a positive integer greater than 1.
- `a` can be any integer (including negative).  You may normalize `a` modulo `m` first.

Return the smallest positive integer between 1 and m-1 that satisfies the equation, or -1 if none exists.

Constraints

1 < m ≤ 10^9, -10^9 ≤ a ≤ 10^9. The solution should run in O(log m) time using the extended Euclidean algorithm.

Example

```python
>>> mod_inverse(3, 11)
4
>>> mod_inverse(10, 17)
12
>>> mod_inverse(2, 4)
-1
```

10 points ~15 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

The inverse exists iff gcd(a, m) == 1.

Use the extended Euclidean algorithm to find coefficients x, y such that a*x + m*y = gcd(a, m).

If gcd != 1, return -1. Otherwise, normalize x to be between 1 and m-1.

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.