How it is calculated
The search uses the extended Euclidean algorithm. If the greatest common divisor is greater than 1, there is no inverse.
a × x ≡ 1 (mod m)
Where the numbers come from
- Number
- Modulus
Example
3 × 5 = 15, and the remainder on division by 7 is 1. So the inverse of 3 modulo 7 is 5.
Questions
How is this different from the ordinary fraction 1/a?
The remainder is an integer from 0 to m − 1, not a decimal fraction.
A negative a?
It is first reduced to a nonnegative remainder.
Where is this useful?
In ciphers, and when solving congruences. Everyday arithmetic usually only needs ordinary division.