Primes, Fermat, Euler and fast modular exponentiation

The fundamental theorem of arithmetic, Fermat's little theorem, square-and-multiply exponentiation worked in full on 5^117 mod 19, and Euler's totient function and theorem.

State the fundamental theorem of arithmetic and factor an integer into its prime powers.
Apply Fermat's little theorem and verify 3^6 = 1 (mod 7) by direct computation.
Compute a modular exponentiation by binary decomposition, reproducing every squaring in 5^117 mod 19.
Compute Euler's totient function directly and via the phi(pq) = (p-1)(q-1) identity, and state Euler's theorem.

22 min read

Intuition

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. That is three separate jobs, and this page covers the tools for all three. Primes are the raw material: $n = pq$ only resists factoring because $p$ and $q$ are hard to find. Fermat’s and Euler’s theorems are what make modular exponentiation predictable instead of chaotic. They are the reason $a^{\varphi(n)}$ always lands back on $1$ , which is exactly the fact RSA decryption depends on. And fast exponentiation is what makes any of this usable at real key sizes: an RSA exponent can run to hundreds of digits, and multiplying a number by itself that many times, one step at a time, is not something a computer finishes in a human lifetime. Binary decomposition turns that into a few hundred squarings instead.

Mechanism

A prime number has exactly two positive divisors, $1$ and itself. It cannot be written as a product of two smaller positive integers. This makes primes the multiplicative building blocks of every integer, a fact strong enough to have its own theorem.

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$ .

Worked example

Answer360 = 2^3 x 3^2 x 5

$360 = 8 \times 45 = 2^3 \times 45$ .
$45 = 9 \times 5 = 3^2 \times 5$ .
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.

Mechanism

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.

Worked example

Answer3^6 = 1 (mod 7)

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

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

Mechanism

Computing $3^6$ directly and then reducing works fine for small numbers, but the source also shows a second route that reduces at every step instead of at the end: $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 one is the more important habit: it keeps every intermediate value small, and it generalises to exponents far too large to compute directly. That generalisation is square-and-multiply.

Mechanism

For a modulus and exponent the size RSA and Diffie-Hellman actually use, computing $a^b$ in full before reducing is not an option: 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.

Worked example

Answer5^117 mod 19 = 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}$ .
$5^1 \bmod 19 = 5$ .
$5^2 \equiv (5^1)^2 = 25 \bmod 19 = 6$ .
$5^4 \equiv (5^2)^2 = 6^2 = 36 \bmod 19 = 17$ .
$5^8 \equiv (5^4)^2 = 17^2 = 289 \bmod 19 = 4$ (since $19 \times 15 = 285$ ).
$5^{16} \equiv (5^8)^2 = 4^2 = 16 \bmod 19 = 16$ .
$5^{32} \equiv (5^{16})^2 = 16^2 = 256 \bmod 19 = 9$ (since $19 \times 13 = 247$ ).
$5^{64} \equiv (5^{32})^2 = 9^2 = 81 \bmod 19 = 5$ (since $19 \times 4 = 76$ ).
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}$ .
$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}$ .

Aside

This reaches the answer by computing powers of two from the bottom up ( $5^1, 5^2, 5^4, \ldots, 5^{64}$ ) and multiplying together the ones the binary expansion calls for. The tracer below implements the same idea the other way round, from the top bit down: it keeps a single running accumulator, squaring it every step and multiplying in $5$ whenever the current bit is $1$ . Both are square-and-multiply; they only differ in which end of the exponent they start from. Type base $5$ , exponent $117$ , modulus $19$ into the tracer to see the second route reach the same answer.

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

base

exponent

modulus

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.

Formula

Fermat's little theorem

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

$p$: a prime number
$a$: any integer not divisible by p

Mechanism

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$ .

Worked example

Answerphi(37) = 36

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

Mechanism

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)$ .

Worked example

Answerphi(35) = 24

$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$ .
Multiples of $5$ below $35$ : $5, 10, 15, 20, 25, 30$ , six numbers.
Multiples of $7$ below $35$ : $7, 14, 21, 28$ , four numbers. ( $35$ itself is excluded by “below 35”.)
No overlap between the two lists, since $\mathrm{lcm}(5, 7) = 35$ is not below $35$ . So $34 - 6 - 4 = 24$ integers remain.
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$ , all $34$ of them, multiples of $5$ and $7$ included, and then states “there are 24 numbers on the list.” The printed list does not match that claim: it is not the coprime set, just the full run of consecutive integers. The same pattern repeats for $\varphi(21)$ below. In both cases the final count is correct; only the printed enumeration is wrong. The coprime lists above are the ones that actually 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.

Worked example

Answerphi(21) = 12

$21 = 3 \times 7$ , both prime.
$\varphi(21) = \varphi(3) \times \varphi(7) = (3-1)(7-1) = 2 \times 6 = 12$ .
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 always 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$ .

Mechanism

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$ .

Worked example

Answer3^4 = 1 (mod 5)

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

$\gcd(3, 5) = 1$ , so Euler’s theorem applies.
$3^4 = 81$ .
$81 \bmod 5$ : $5 \times 16 = 80$ , so $81 \bmod 5 = 1$ .
$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.

Source

Week 4 Number Theory PDF