Modular Inverse
x with ax = 1 mod m. Via extended Euclid, or a^(m-2) when m is prime.
Multiples, 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.
Cost
- Best
- O(log m)
- Average
- O(log m)
- Worst
- O(log m)
- Space
- O(1)
Taught by the same lesson
Multiples, Powers, Pascal covers these too, in the same run.