Inputs
Any integer.
Integer ≥ 2.
Try
Result
No inverse
gcd(6, 9) = 3, not 1, so 6 has no inverse mod 9.
Only integers coprime to the modulus have one.
3⁻¹ mod 7
5
3 · (-2) + 7 · (1) = 1
3⁻¹ ≡ 5 (mod 7)
((-2 % 7) + 7) % 7 = 5
- gcd(a, n)
- 1
- x (raw)
- -2
- Steps
- 2
Algorithm steps
| i | q | r | x | y |
|---|
Every row satisfies r = a·x + n·y. The last nonzero r is gcd(a, n); when it's 1, that row's x (reduced mod n) is the inverse above — this table always shows the full trace, even when no inverse exists, since it's what proves the gcd.