Why is using a prime modulus (like 31) better than a composite modulus (like 26) for the affine cipher, and what practical problem does it introduce?

A prime modulus maximizes the key space because every non-zero value of $a$ is coprime to a prime — but it creates more cipher symbols than plaintext symbols, requiring extra characters.

With mod 26 (composite, $26 = 2 \times 13$):

• Only 12 of 25 non-zero values for $a$ satisfy $\gcd(a, 26) = 1$
• Key space: $12 \times 26 = 312$ keys

With mod 23 (prime):

• All 22 non-zero values for $a$ are valid (every non-zero element is coprime to a prime)
• Key space: $22 \times 23 = 506$ keys (or 462 excluding trivial)
• Problem: 23 < 26, so letters X, Y, Z have no encoding → you lose characters

With mod 31 (prime):

• All 30 non-zero values for $a$ are valid
• Key space: $30 \times 31 = 930$ keys — nearly 3x larger than mod 26
• Problem: 31 > 26, so you need 5 extra symbols (e.g., space, ?, !, comma, period) to fill all 31 slots
• The ciphertext now contains symbols beyond A-Z, which may be undesirable

Key insight: Primes maximize the multiplicative group, but the cipher's alphabet size must match the modulus exactly. This is a design trade-off between security (larger key space) and practicality (matching the alphabet).

Go deeper:

• Affine cipher (Wikipedia) — how the modulus choice sets the key space.