Flip open any cryptography textbook and you will see the phrase "let p be a large prime" repeated almost religiously. RSA uses primes. Diffie–Hellman uses primes. Elliptic-curve cryptography uses primes. Why? Composite moduli like 15 or 100 also wrap numbers into a finite range.

The short answer is that prime moduli give you three things at once that composite moduli do not:

  1. Every nonzero residue has a multiplicative inverse — so division works, and \mathbb{Z}/p\mathbb{Z} is a field, not just a ring.
  2. Fermat's little theorem — a^{p-1} \equiv 1 \pmod p — gives a clean, universal identity that cryptographic protocols rely on for correctness.
  3. The discrete logarithm problem is hard mod a large prime, which is what makes the ciphers secure.

Composite moduli break all three properties in ways that matter. Let us see how.

Property 1: Every nonzero residue is invertible

Cryptographic protocols constantly need to divide: encrypting is often "multiply by a secret", decrypting is "multiply by its inverse". If the inverse does not exist, decryption fails.

Mod a prime p, every nonzero residue a \in \{1, \dots, p-1\} has a unique multiplicative inverse. The reason is that \gcd(a, p) = 1 automatically: the only divisors of p are 1 and p, so no element of \{1, \dots, p-1\} shares a factor with p. By Bézout's identity, you can always solve a x + p y = 1, and reducing mod p gives a \cdot x \equiv 1 \pmod p.

Mod a composite n, this breaks. Take n = 12 and a = 4: \gcd(4, 12) = 4, and no integer x satisfies 4x \equiv 1 \pmod{12}. The multiplication table of \mathbb{Z}/12\mathbb{Z} has entire rows with no 1 in them — see the mod-7 multiplication table satellite for the visual signature.

Every nonzero element invertible is the defining property of a field. So \mathbb{Z}/p\mathbb{Z} for prime p is a finite field, written \mathbb{F}_p. Cryptographers want to live inside a field rather than a ring because fields are where linear equations have unique solutions and division always works.

Property 2: Fermat's little theorem

A prime modulus comes with a free universal identity:

a^{p-1} \equiv 1 \pmod p \qquad \text{for every } a \text{ with } \gcd(a, p) = 1.

This is Fermat's little theorem — see the sibling demo for a draggable verification. The immediate corollary: exponents only matter modulo p - 1. When you compute a^e \bmod p for a huge e, first reduce e modulo p - 1 and work with a small number.

Cryptographic protocols exploit this constantly. In RSA, the decryption exponent d is chosen so that e \cdot d \equiv 1 \pmod{\phi(n)}, and correctness follows from Fermat–Euler. In Diffie–Hellman, Fermat guarantees every element generates a cyclic subgroup whose size divides p - 1 — exactly the structure the protocol hides information inside.

For a composite n you get Euler's theorem, a^{\phi(n)} \equiv 1 \pmod n when \gcd(a, n) = 1 — but \phi(n) is hard to compute without knowing n's factorisation, which is exactly the hard problem RSA hides behind.

Property 3: Discrete log is hard mod a large prime

Cryptography needs a one-way function — easy to compute, hard to invert. Modular exponentiation mod a large prime is the workhorse.

Given a prime p, a generator g of \mathbb{F}_p^*, and a secret exponent x, computing y \equiv g^x \pmod p by repeated squaring takes a handful of multiplications even for x with hundreds of digits. Inverting — given p, g, y, find the x — is the discrete logarithm problem, and for primes thousands of bits long, no known classical algorithm solves it in reasonable time.

The problem is hard specifically because \mathbb{F}_p^* is cyclic with no useful substructure. For a composite modulus, the Chinese Remainder Theorem splits the problem into smaller pieces — one per prime factor — and the Pohlig–Hellman algorithm makes the whole thing as hard as the largest prime factor, not the full modulus. That is why cryptographers insist on primes, often safe primes where p - 1 itself has a large prime factor.

A tangible example: mini Diffie–Hellman mod 23

Alice and Bob want to agree on a shared secret over a public channel. They agree publicly on a prime p = 23 and a generator g = 5.

Diffie-Hellman key exchange mod 23Alice on the left and Bob on the right. Alice picks secret a equals 6 and sends A equals 8 to Bob. Bob picks secret b equals 15 and sends B equals 19 to Alice. Both compute the shared secret 2 by raising the other's public value to their own secret. Alice secret a = 6 A = 5^6 mod 23 A = 8 receives B = 19 s = 19^6 mod 23 s = 2 Bob secret b = 15 B = 5^15 mod 23 B = 19 receives A = 8 s = 8^15 mod 23 s = 2 send A send B
Diffie–Hellman mod $p = 23$ with generator $g = 5$. Alice and Bob exchange $A = g^a$ and $B = g^b$ publicly, then each raises the other's value to their own secret exponent. Both arrive at $g^{ab} \bmod p = 2$ without ever sending their secrets. An eavesdropper who sees $A$ and $B$ must solve the discrete log problem to recover $a$ or $b$.

Work the protocol by hand.

Alice picks a secret a = 6 and computes A = 5^6 \bmod 23.

5^2 = 25 \equiv 2 \pmod{23}. So 5^4 \equiv 4, and 5^6 = 5^4 \cdot 5^2 \equiv 4 \cdot 2 = 8 \pmod{23}.

Alice sends A = 8 to Bob.

Bob picks a secret b = 15 and computes B = 5^{15} \bmod 23.

5^{15} = 5^{8} \cdot 5^{4} \cdot 5^{2} \cdot 5^{1}. From above, 5^2 \equiv 2, 5^4 \equiv 4, 5^8 \equiv 16 \pmod{23}.

So B \equiv 16 \cdot 4 \cdot 2 \cdot 5 = 640. Reduce: 640 = 27 \cdot 23 + 19, so B \equiv 19 \pmod{23}.

Bob sends B = 19 to Alice.

Shared secret. Alice computes s = B^a = 19^6 \bmod 23. Bob computes s = A^b = 8^{15} \bmod 23.

Both get the same answer because 19^6 \equiv (5^{15})^6 = 5^{90} and 8^{15} \equiv (5^6)^{15} = 5^{90} — both equal g^{ab} \bmod p.

Compute 19^6 \bmod 23: 19 \equiv -4, so 19^6 \equiv (-4)^6 = 4^6 = 4096. Reduce: 4096 = 178 \cdot 23 + 2, so s \equiv 2 \pmod{23}.

Why Fermat matters here: the exponents a and b live in \{1, 2, \dots, p-2\} because g^{p-1} \equiv 1 \pmod p collapses anything larger. The secret space is exactly p - 2 choices, and because 5 is a generator of \mathbb{F}_{23}^*, every nonzero residue is a possible shared secret with equal likelihood.

An eavesdropper who sees p = 23, g = 5, A = 8, B = 19 must solve "5^x \equiv 8 \pmod{23}" to recover Alice's secret — the discrete log problem. For p = 23 you can brute-force it (x = 6); for a 2048-bit prime, there are more candidate x than atoms in the observable universe.

What breaks with a composite modulus

Try Diffie–Hellman mod n = 15 = 3 \times 5. The group (\mathbb{Z}/15\mathbb{Z})^* has only \phi(15) = 8 elements, not 14 — the residues 3, 5, 6, 9, 10, 12 are missing because they share factors with 15. By CRT, the discrete log problem splits into one problem mod 3 and one mod 5, trivially easy together. No single generator hits every nonzero residue. The arithmetic still happens, but the cryptographic guarantees do not.

Exceptions that prove the rule

Two places cryptography uses composite moduli — and both still rely on primes underneath. RSA uses n = pq for secret primes p, q; the algebra runs inside \mathbb{F}_p and \mathbb{F}_q separately via CRT. Elliptic curves over \mathbb{F}_p replace exponentiation with point addition, but the coordinate field is still \mathbb{F}_p for a prime p. Primes are doing the actual algebraic heavy lifting either way.

The takeaway

When your textbook writes "let p be a large prime", it is asking for three things at once, in one word: a field (so division works), Fermat's little theorem (so exponents behave cleanly modulo p-1), and a hard discrete log (so secrecy survives against eavesdroppers). No composite modulus delivers all three. The insistence is not fetishism — it is the minimum algebraic requirement for modern cryptography to work.

Related: Modular Arithmetic · Mod 7 Multiplication Table — Why ℤ/7ℤ Is a Field · Fermat's Little Theorem Demo · The Chinese Remainder Theorem in One Sentence · Modular Inverse Finder