Fermat's Little theorem

We present now some notable congruence relations

Proposition 4.1.1. For any prime p and x,y ∈ ℤ the following relation holds

(x + y)^p ≡ x^p + y^p (mod p)

Proof. From the binomial identity

(x + y)^{p} = x^{p} + \sum_{k = 1}^{p - 1} (\binom{p}{k}) x^{p - k} y^{k} + y^{p}

it is enough to prove that the summation is divisible by p. This is true because in the summation, it results k < p and p − k < p, so each binomial coefficient is an integer with p as factor. □

Theorem 4.1.2 (Fermat's Little theorem). Let a an integer and p a prime number. Then

a^p ≡ a (mod p) (4.4)

If a is divisible by p, then (4.4) is trivially true, as a^p ≡ a ≡ 0 (mod p). If a is not divisible by p, then suppose a ≥ 0, we use induction using a itself as induction variable. If a = 0 the result is obvious. Supposing true the result for a > 0 we prove it for a + 1. Owing to eq (4.4)

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

Since 1^p ≡ 1 and a^p ≡ a for the inductive hypothesis, it follows

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

the expected result.

We suppose now a < 0. Thus 0 ≡ 0^p = (a + (−a))^p ≡ a^p + (−a)^p (mod p). Since −a >0, for what we already proved in the first part: (−a)^p ≡ −a, thus 0 ≡ a^p −a, i.e. a^p ≡ a. □

Corollary 4.1.3. If gcd(a, p) = 1, then

a^p−1 ≡ 1 (mod p)

From proposition 4.1.2, p | a^p − a = a(a^p−1 − 1) and if gcd(a, p) = 1, then p | a^p−1 − 1.□

« Modular Arithmetic Index Divisibility criteria »