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 ap− 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 52 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 ...