Fermat's Little Theorem and Euler's Theorem
Created:
2017-07-23
Updated:
2017-07-23
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 }
- 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*
.
- Finally, we prove that
X = Zp*
by showing that ifi ≠ j
thena·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 }
- 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*
- 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)
∎