Fermat’s Little theorem states that if p is a prime number and a is an integer not divisible by p, then a^(p-1) ≡ 1 (mod p).

Euler’s theorem extends this to any positive integer n, stating that a^φ(n) ≡ 1 (mod n), where φ(n) is Euler’s totient function.

These theorems provide mathematical properties and tools that are key building blocks for many cryptographic primitives and protocols.

Fermat’s Little Theorem

Given two numbers a and p such that p is prime and (a,p) = 1, then

a^(p-1) ≡ 1 (mod p)

Proof

First we need to prove equality of the sets:

Zp* = { 1, 2, 3, ..., p-1 }
X = { a mod p, 2·a mod p, ... , (p-1)·a mod p }

1. Prove that X ⊆ Zp*

Since (a,p) = 1 and (j,p) = 1, for all j ∈ Zp*

1 = a·x + p·y
1 = j·z + p·k
→  1 = a·j·w + p·u  →  w is inverse of a·j mod p 
→  (a·j,p) = 1

For Euclidean algorithm: 1 = (a·j, p) = (p, a·j mod p). Follows that a·j mod p ∈ Zp*.

2. Finally, we prove that X = Zp* by showing that if i ≠ j then a·i ≢ a·j.

This is equivalent to prove that if a·i ≡ a·j (mod p) then i = j.

a·i ≡ a·j (mod p)
→ since (a,p) = 1 there exists the inverse of a modulo p
→ i ≡ j (mod p) and because both i, j < p follows that i = j

Because X = Zp* we can now write:

(p-1)! = (a mod p)·(2·a mod p) · ... · ((p-1)·a mod p)
→ (p-1)! ≡ (a mod p)·(2·a mod p) · ... · ((p-1)·a mod p) (mod p)
         ≡ (a · 2·a · ... · (p-1)·a) (mod p)
         ≡ a^(p-1) · 1·2·(p-1) (mod p)
         ≡ a^(p-1) · (p-1)! (mod p)

Every factor in (p-1)! is invertible modulo p, thus the thesis follows.

∎

Corollary

Given a and p with p prime and (a,p) = 1. Then, for any integer k

a^k ≡ a^(k mod p-1) (mod p)

Proof

For the division theorem, there are unique q and r such that:

k = (p-1)·q + r,  with r = k mod p-1

a^k = a^[(p-1)·q + r] = a^[(p-1)·q] · a^r

For the Fermat’s Little Theorem a^(p-1) ≡ 1 (mod p), then:

a^k ≡ 1^q ⋅ a^r ≡ a^r (mod p)

∎

Euler’s Theorem

Given n ≥ 1 and (a,n) = 1 then:

a^φ(n) = 1 (mod n)

With φ(n) the Euler’s Totient function that counts the number of elements in Zn that are coprime to n (|Zn*|).

Proof

Very similar to the Little Fermat theorem, first we need to prove the equality of the sets:

Zn* = { x1, x2, ..., x_φ(n) }
X = { a·x1 mod n, a·x2 mod n, ..., a·x_φ(n) mod n }

1. Prove that X ⊆ Zn'

(a⋅xi, n) = 1 (mod n)

Given that (a,n) = 1 and (xi,n) = 1

1 = a·w + n·z
1 = xi·k + n·y = 1
→ 1 = a·xi·u + n·q   (u is the inverse of a·xi modulo n)
→ (a·xi,n) = 1

For Euclidean algorithm:

1 = (a·xi, n) = (n, a·xi mod n)

Thus a·xi mod n ∈ Zp*

2. Finally, we prove that X = Zn*

If a·xi ≡ a·xj (mod n)
→ because (a,n) = 1 there exists the inverse of a modulo n
→ xi ≡ xj (mod n) and because both xi, xj < n follows that xi = xj

x1·...·x_φ(n) = (a·x1 mod n)·...·(a·x_φ(n) mod n)

→ x1·...·x_φ(n) ≡ (a·x1 mod n)·...·(a·x_φ(n) mod n) (mod n)
                ≡ (a·x1 · ... · a·x_φ(n)) (mod n)
                ≡ a^φ(n) · x1·...·x_φ(n) (mod n)

Every xi has an inverse modulo n, thus 1 ≡ a^φ(n) (mod n)

∎

Corollary

Given a and n with (a,n) = 1. Then, for any integer k

a^k = a^(k mod φ(n))  (mod n)

Proof

k = φ(n)·q + r, with r = k mod φ(n)

a^k = a^[φ(n)·q + r] = a^[φ(n)·q] · a^r

For Euler’s Theorem a^φ(n) ≡ 1 (mod n), then:

a^k ≡ 1^q · a^r (mod n)

∎