Modular Inverse
x with ax = 1 mod m; via extended Euclid, or a^(m-2) when m is prime.
Decision · step 10 of 12Multiples, Powers, Pascal: Inverse of 3 mod 11
3^9 = 5 x 3 mod 11 = 15 mod 11 = 4. That is 3^9, the inverse: 3 x 4 = 12 = 1 x 11 + 1.
What you will see
Both routes side by side; they land on the same x.
Cost
| Best | O(log m) |
|---|---|
| Average | O(log m) |
| Worst | O(log m) |
| Space | O(1) |
How you work with it here
play it through, compare two runs.
Screen readers: Numbers announce their value and role; each step announces the arithmetic performed.
Reduced motion: Values crossfade; no travelling digits.
Taught by the same lesson
Multiples, Powers, Pascal covers these too, in the same run.