 # 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 }
``````
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*`.

1. 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*`

1. 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)
``````