O'Reilly logo

Information Theory, Coding and Cryptography by Mandal, Nilotpal Manna, Arijit Saha

Stay ahead with the world's most comprehensive technology and business learning platform.

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

Start Free Trial

No credit card required

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

Start Free Trial

No credit card required