Information Theory, Coding and Cryptography

Appendix A

Some Related Mathematics

A.1  FERMAT’S LITTLE THEOREM

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² 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:

 

a, 2a, 3a, ..., (p − 1)a

 

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