Number Theory and its Applications

5 Fermat's Little Theorem

“Perhaps, posterity will thank me for having shown that the ancients did not know anything.”

– Pierre De Fermat

5.1 Introduction

The famous French Mathematician Pierre de Fermat first wrote what would become his “Little Theorem” in 1640. It states that for any prime number p and any integer a the expression (a^p − a) is divisible by p as long as p does not divide a(the pair are relatively prime). Although a number n that does not divide aⁿ − a for some a must be a composite number but the converse is not necessarily true. An example, in the later section of the chapter, will justify the above argument. Thus, Fermat’s theorem gives a test that is necessary but not sufficient for primality. Also the theorem is applicable ...