# rsa / Fermat & Euler: 2 Important Theorems — Number Theory

Part of my series explaining the RSA Algorithm

In 1640 Pierre de Fermat wrote in a letter to a friend.

If p is a prime and a is any integer not divisible by p, then aᵖ⁻¹ − 1 is divisible by p.

Unlike most of the things I say to my friends, Fermat was right. Fermat never proved it though. He left the job to Leonhard Euler, known here as the busiest person in all of mathematical history. In 1736 Euler showed that Fermat had been right, and went on to extend the claim too.

Fermat’s Little Theorem

Fermat had bigger fish to fry, so this was his little theorem. It states that for any prime, p and integer a which is coprime to p: aᵖ⁻¹ % p = 1.

Why was Fermat right?

The list of numbers a, 2a, 3a, …, (p-1)a are all coprime to p, because p is prime. If we mod p each of these numbers we are guaranteed to produce a list of all the numbers between 1 & p-1. This is because there will be p - 1 distinct results. We can prove that they will be distinct.

> if `k` & `m` are two values between `1` & `p - 1`
> to prove they are NOT distinct we would want to find
ka ≡ ma (mod p)

> because of the cancellation rule
k ≡ m (mod p)

> because `k` & `m` were defined as being less than `p`
k = m

(For a reminder of the cancellation rule, take a look at rule 2 in our explanation of 4 Important Rules of Modular Arithmetic)

So we have shown that given the list a, 2a, 3a, …, (p-1)a (mod p), we would get the full set of numbers 1 -> p - 1. Ordering those results would give us the set: 1, 2, …, p-1.

An example might make things clearer:

p = 7, a = 3

> a, 2a, 3a, ..., (p-1)a
1(3), 2(3), 3(3), 4(3), 5(3), 6(3)
3, 6, 9, 12, 15, 18

> all `mod p`
3, 6, 2, 5, 1, 4

> ordering the results
1, 2, 3, 4, 5, 6

With this understanding we can prove Fermat’s Little Theorem.

> we know that
a, 2a, ..., (p-1)a ≡ 1, 2, ..., p-1 (mod p)

> multiplying all elements
a x 2a x ... x (p-1)a ≡ 1 x 2 x ... x (p-1) (mod p)

> simplifies
aᵖ⁻¹(p-1)! ≡ (p-1)! (mod p)

> cancel `(p-1)!`

> giving us
aᵖ⁻¹ ≡ 1 (mod p)

We’ve derived Fermat’s Little Theorem. This works for any positive integer a and prime p.

Euler’s Theorem

Having proved Fermat’s Little Theorem, Euler decided to keep going. He was able to show that for any two coprime integers, neither necessarily coprime: aᵠ⁽ⁿ⁾ ≡ 1 (mod n). 𝛗 refers to Euler’s Totient Function, which we explored previously. The Totient function of any integer n, returns the number of n’s coprimes smaller than n.

Unlike Fermat’s Little Theorem, Euler’s extension removed the need for the modulus to be a prime number. Thankfully though, we’ve done most of the work to prove this already.

Remember how, with Fermat’s Little Theorem, all of a’s multiples (mod p), gave the numbers 1 -> p-1. That list of numbers, 1 -> p-1 were p’s coprimes, given that p is prime. In this case the modulus n is not prime, but the list of n’s coprimes multiplied by a, all (mod n), still produces n’s coprimes. For example

> remembering that
𝛗(n) = Number of n's coprimes

n = 10

> n's coprimes
1, 3, 7, 9

a x 3a x 7a x 9a ≡ 1 x 3 x 7 x 9 (mod n)

> where n = 10, this gives us the number of "a" factors
aᵠ⁽¹⁰⁾

aᵠ⁽¹⁰⁾ x (1 x 3 x 7 x 9) ≡ (1 x 3 x 7 x 9) (mod n)

> cancel the coprime multiplication
aᵠ⁽¹⁰⁾ ≡ 1 (mod n)

Conclusion

Fermat’s Little Theorem & Euler’s Theorem are very important to Number Theory. They help solve cases of the Carmichael Function, which we covered in depth. They are interesting in isolation too, as an example use of Euler’s Totient Function.

And it all began with a letter to a friend almost 400 years ago.