1st Course for high Diploma, Number Theory Lecture 5: Fermat s Theorem

4.1 Fermat’s theorem

Theorem 4.1.1. (Fermat’s theorem). Let p be a prime and suppose that p is not divide a. Then a p?1 ?1 (mod p).

Proof. The ?rst p?1 positive multiples of a is the integers
a, 2a, 3a, ..., (p ?1)a

None of these numbers is congruent modulo p to any other, nor is any congruent to zero. Indeed, if it happened that ra ? sa (mod p), 1 ?r < s ? p ?1 then r ? s (mod p), which is impossible.

Therefore, the previous set of integers must be congruent modulo p to 1,2,3,...,p?1. Multiplying all these congruences together results

a ·2 a ·3 a ···(p ?1) a ? 1·2·3···(p?1) (mod p)

whence a p?1 (p ?1)! ? (p?1)! (mod p). By canceling (p?1)! from both sides of the preceding congruence (since p is not divide (p?1)!), so a p?1 ?1 (mod p), which is Fermat’s theorem.

Corollary 4.1.2. If p is a prime, then a p ? a (mod p) for any integer a.

Proof. H.W.

Fermat’s theorem has many applications and solving some problems in number theory. For example, how to verify that

538 ? 4(mod11).
One can know 510 ?1 (mod 11) form (Fermat’s theorem) and it can compute that as

538 =510·3+8 =(510)3(52)4 ?13 ·34 ?81? 4 (mod 11).