Primes, Fermat, Euler and fast modular exponentiation

Primes are the building blocks, and every integer factors into them in exactly one way

RSA key generation needs two large primes, a count of how many numbers are coprime to their product, and an exponent computed against that count. This page covers the tools for all three. Primes come first: $n = pq$ only resists factoring because $p$ and $q$ are hard to find.

A prime number has exactly two positive divisors, $1$ and itself. It cannot be written as a product of two smaller positive integers. The fundamental theorem of arithmetic states that any integer $a > 1$ factors into primes in exactly one way: $a = p_1^{a_1} \times p_2^{a_2} \times \ldots \times p_t^{a_t}, \qquad p_1 < p_2 < \ldots < p_t \text{ prime.}$ Uniqueness is the load-bearing part: there is no second, different set of prime powers that also multiplies out to $a$.

Try it — worked example

Write 360 as a product of primes.

Show answer and steps

Answer360 = 2^3 x 3^2 x 5

1. $360 = 8 \times 45 = 2^3 \times 45$.
2. $45 = 9 \times 5 = 3^2 \times 5$.
3. Combining: $360 = 2^3 \times 3^2 \times 5$. Check: $8 \times 9 \times 5 = 360$.

Pitfall

The Week 4 number-theory supplement’s own second example, factoring $36$, prints $36 = 2^2 \times 3^3$. That is wrong: $2^2 \times 3^3 = 4 \times 27 = 108$, not $36$. The correct factorisation is $36 = 2^2 \times 3^2$ ($4 \times 9 = 36$); the exponent on $3$ is $2$, not $3$. The $360$ example above is printed correctly in the source and needs no correction.

Fermat’s little theorem makes powers predictable, and square-and-multiply makes them cheap

Fermat’s little theorem states that for a prime $p$ and any integer $a$ not divisible by $p$, $a^{p-1} \equiv 1 \pmod{p}.$ Raising $a$ to one less than the prime always lands on $1$, modulo that prime. This is why $a^{\varphi(n)}$ lands back on $1$ in the generalisation below, which is the fact RSA decryption depends on.

Formula

Fermat's little theorem

$$a^{p-1} \equiv 1 \pmod{p}$$

$p$

a prime number

$a$

any integer not divisible by p

Try it — worked example

Check Fermat’s little theorem for p = 7, a = 3: what is 3^6 mod 7?

Show answer and steps

Answer3^6 = 1 (mod 7)

Take $p = 7$, $a = 3$. Fermat predicts $3^{7-1} = 3^6 \equiv 1 \pmod{7}$.

1. $3^6 = 729$.
2. $729 \bmod 7$: $7 \times 104 = 728$, and $729 - 728 = 1$. So $729 \bmod 7 = 1$.
3. $3^6 \equiv 1 \pmod{7}$, confirming the theorem.

Computing $3^6$ directly and then reducing works for small numbers, but the source also shows a second route that reduces at every step: $3 \bmod 7 = 3$, $3^2 \bmod 7 = 9 \bmod 7 = 2$, and then $3^6 = 3^2 \times 3^2 \times 3^2 \equiv 2 \times 2 \times 2 = 8 \equiv 1 \pmod{7}.$ Both routes agree. The second is the habit that matters: it keeps every intermediate value small and generalises to exponents far too large to compute directly.

At the size RSA and Diffie-Hellman use, computing $a^b$ in full before reducing is not an option, because the intermediate number would run to thousands of digits. Square-and-multiply fixes this by writing the exponent $b$ in binary and building the answer from repeated squarings of $a$, mod $n$, at every step, combining only the squarings that correspond to a $1$ bit.

Try it — worked example

Use square-and-multiply to compute 5^117 mod 19.

Show answer and steps

Answer5^117 mod 19 = 1

1. Write $117$ in binary: $117 = 1110101_2$, i.e. $117 = 2^0 + 2^2 + 2^4 + 2^5 + 2^6 = 1 + 4 + 16 + 32 + 64$. So $5^{117} = 5^1 \times 5^4 \times 5^{16} \times 5^{32} \times 5^{64}$.
2. $5^1 \bmod 19 = 5$.
3. $5^2 \equiv (5^1)^2 = 25 \bmod 19 = 6$.
4. $5^4 \equiv (5^2)^2 = 6^2 = 36 \bmod 19 = 17$.
5. $5^8 \equiv (5^4)^2 = 17^2 = 289 \bmod 19 = 4$ (since $19 \times 15 = 285$).
6. $5^{16} \equiv (5^8)^2 = 4^2 = 16 \bmod 19 = 16$.
7. $5^{32} \equiv (5^{16})^2 = 16^2 = 256 \bmod 19 = 9$ (since $19 \times 13 = 247$).
8. $5^{64} \equiv (5^{32})^2 = 9^2 = 81 \bmod 19 = 5$ (since $19 \times 4 = 76$).
9. Combine the terms needed for $117 = 1 + 4 + 16 + 32 + 64$: $5^{117} \equiv 5^1 \times 5^4 \times 5^{16} \times 5^{32} \times 5^{64} \equiv 5 \times 17 \times 16 \times 9 \times 5 \pmod{19}$.
10. $5 \times 17 \times 16 \times 9 \times 5 = 61200$. $61200 \bmod 19$: $19 \times 3221 = 61199$, so $61200 \bmod 19 = 1$. Thus $5^{117} \equiv 1 \pmod{19}$.

That worked example builds the powers of two from the bottom up and multiplies together the ones the binary expansion calls for. The tracer below runs the same idea from the top bit down: one running accumulator, squared every step, with $5$ multiplied in whenever the current bit is $1$. Type base $5$, exponent $117$, modulus $19$ into it to reach the same answer.

Modular exponentiation tracer

Trace square-and-multiply bit by bit: the exponent in binary, the squaring step, the conditional multiply, and the accumulator.

base

exponent

modulus

Run

Exponent in binary

i	bit	square	multiply	accumulator

Exam detail

The point of this method is the operation count. Multiplying $a$ by itself $b - 1$ times is $O(b)$ multiplications, infeasible once $b$ has hundreds of digits. Square-and-multiply needs one squaring per bit of $b$ and one extra multiply per $1$ bit, so the cost is $O(\log b)$ modular multiplications: for a 2048-bit RSA exponent, roughly 2048 squarings instead of $2^{2048}$ multiplications. Diffie-Hellman key exchange, covered in Diffie-Hellman key exchange, runs on exactly this operation.

The totient counts the numbers coprime to n, and for a product of two primes it is (p-1)(q-1)

Fermat’s little theorem only counts, implicitly, the $p - 1$ nonzero residues mod a prime $p$. Euler’s totient function $\varphi(n)$ generalises that count to any modulus: $\varphi(n)$ is the number of positive integers less than $n$ that are relatively prime to $n$. When $n = p$ is prime, every integer from $1$ to $p - 1$ is coprime to $p$, so $\varphi(p) = p - 1$.

Try it — worked example

Find φ(37).

Show answer and steps

Answerphi(37) = 36

1. $37$ is prime.
2. Every integer from $1$ through $36$ shares no factor with a prime, so all $36$ of them are coprime to $37$.
3. $\varphi(37) = 36$.

For $n$ that is not prime, the direct method is to list every integer below $n$ and remove the ones that share a factor with $n$. The supplement demonstrates this on $\varphi(35)$.

Try it — worked example

Find φ(35) by listing the numbers that are not coprime to 35.

Show answer and steps

Answerphi(35) = 24

1. $35 = 5 \times 7$, so an integer from $1$ to $34$ fails to be coprime to $35$ exactly when it is a multiple of $5$ or of $7$.
2. Multiples of $5$ below $35$: $5, 10, 15, 20, 25, 30$, six numbers.
3. Multiples of $7$ below $35$: $7, 14, 21, 28$, four numbers. ($35$ itself is excluded by “below 35”.)
4. No overlap between the two lists, since $\mathrm{lcm}(5, 7) = 35$ is not below $35$. So $34 - 6 - 4 = 24$ integers remain.
5. The coprime set is $\{1, 2, 3, 4, 6, 8, 9, 11, 12, 13, 16, 17, 18, 19, 22, 23, 24, 26, 27, 29, 31, 32, 33, 34\}$, $24$ numbers. $\varphi(35) = 24$.

Pitfall

The Week 4 supplement’s own worked version of this example lists every integer from $1$ through $34$, multiples of $5$ and $7$ included, and then states “there are 24 numbers on the list.” The printed list is just the full run of consecutive integers, not the coprime set. The same happens for $\varphi(21)$ below. In both cases the final count is correct; only the printed enumeration is wrong. The coprime lists on this page are the ones that belong to $\varphi(35)$ and $\varphi(21)$.

Formula

Totient of a product of two primes

$$\varphi(pq) = \varphi(p) \times \varphi(q) = (p-1)(q-1)$$

$p, q$

two distinct primes

$n = pq$

their product

This is the identity RSA key generation runs directly, and the reason listing every integer below n is never actually necessary when n's factorisation is known.

Try it — worked example

Find φ(21) using the product-of-two-primes rule.

Show answer and steps

Answerphi(21) = 12

1. $21 = 3 \times 7$, both prime.
2. $\varphi(21) = \varphi(3) \times \varphi(7) = (3-1)(7-1) = 2 \times 6 = 12$.
3. Direct check: the integers from $1$ to $20$ coprime to $21$ (excluding multiples of $3$ and of $7$) are $\{1, 2, 4, 5, 8, 10, 11, 13, 16, 17, 19, 20\}$, $12$ numbers, agreeing with the formula.

Exam detail

Whenever $n$‘s prime factorisation is already known, the $(p-1)(q-1)$ identity is faster and safer than listing and counting. RSA key generation never enumerates anything: it computes $\varphi(n) = (p-1)(q-1)$ directly from the two primes it just generated. See extended Euclid and modular inverses for how $\varphi(n)$ feeds into finding the private exponent $d$.

Euler’s theorem extends Fermat’s to any modulus coprime to the base

Euler’s theorem generalises Fermat’s little theorem from a prime modulus to any modulus, provided the base and modulus are coprime: $a^{\varphi(n)} \equiv 1 \pmod{n}, \qquad \gcd(a, n) = 1.$ An equivalent form is $a^{\varphi(n)+1} \equiv a \pmod{n}$. Setting $n = p$ prime recovers Fermat’s theorem exactly, since $\varphi(p) = p - 1$.

Try it — worked example

Check Euler’s theorem for a = 3, n = 5: what is 3^φ(5) mod 5?

Show answer and steps

Answer3^4 = 1 (mod 5)

Take $a = 3$, $n = 5$. $\varphi(5) = 4$, since $5$ is prime.

1. $\gcd(3, 5) = 1$, so Euler’s theorem applies.
2. $3^4 = 81$.
3. $81 \bmod 5$: $5 \times 16 = 80$, so $81 \bmod 5 = 1$.
4. $3^{\varphi(5)} = 3^4 \equiv 1 \pmod{5}$, as the theorem predicts.

Recall

Why does Fermat's little theorem count as a special case of Euler's theorem, rather than a separate result?

Euler’s theorem says $a^{\varphi(n)} \equiv 1 \pmod{n}$ for any $a$ coprime to $n$. When $n$ is a prime $p$, every integer from $1$ to $p-1$ is automatically coprime to $p$, and $\varphi(p) = p - 1$. Substituting recovers $a^{p-1} \equiv 1 \pmod{p}$ exactly: Fermat’s statement, with no extra assumption needed beyond $n$ being prime.