The modular inverse

Dividing by 3 is the same as multiplying by 1/3. In modular arithmetic, 1/3 does not exist — but a substitute does.

The definition

The inverse of a modulo n is the integer x such that:

a × x ≡ 1  (mod n)

Example: modulo 26, the inverse of 3 is 9, since 3 × 9 = 27 ≡ 1 (mod 26).

When does it exist?

Not always! This is the crucial point:

a has an inverse modulo n if and only if pgcd(a, n) = 1, that is, if a and n are relatively prime.

Modulo 26, the number 13 has no inverse, because pgcd(13, 26) = 13. Whatever you multiply 13 by, you will never end up with 1 modulo 26.

This is why the affine cipher y = ax + b (mod 26) requires that a be coprime with 26: without an inverse, decryption would be impossible and several plaintext letters would result in the same ciphertext letter.

Understanding this through an example

Why is pgcd = 1 necessary? If a and n share a common divisor d > 1, then all multiples of a modulo n are also multiples of d. However, 1 is not a multiple of d. Therefore, 1 can never be reached.

What is it for?

In RSA, the private key d is precisely the modular inverse of the public key e. It is this relationship that ensures that decryption exactly reverses encryption.

The extended Euclidean algorithm calculates this inverse quickly, even for numbers with several hundred digits.