With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

No credit card required

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

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

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

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

No credit card required