Fermat’s Little Theorem is often used in number theory in the testing of large primes and simply states as follows.

**Theorem A.1:** Let* p* be a prime which does not divide the integer *a*, then *a*^{p− 1} = 1 (mod *p*).

In more simple language, it may be stated that if *p* is a prime that is not a factor of* a,* then when* a* is multiplied (*p −* 1) times and the result is divided by *p*, we get a remainder of 1. For example, if we use *a* = 5 and* p* = 3, the rule says that 5^{2} divided by 3 will have a remainder of 1. In fact, 25/3 does have a remainder of 1.

**Proof:** Start by listing the first (*p −* 1) positive multiples of a:

Suppose that* ra* and* sa* are the same modulo *p*, then we ...

Start Free Trial

No credit card required