### Number Theory

Number theory is the study of the set of positive whole numbers 1,2,3,4,5,6,7,…,which are often called the set of natural numbers. We will especially want to study the relationships between different sorts of numbers. Since ancient times, people have separated the natural numbers into a variety of different types. Here are some familiar and not-so-familiar examples: odd 1,3,5,7,9,11,… even 2,4,6,8,10,… square 1,4,9,16,25,36,… cube 1,8,27,64,125,… prime 2,3,5,7,11,13,17,19,23,29,31,… composite 4,6,8,9,10,12,14,15,16,… 1 (modulo 4) 1,5,9,13,17,21,25,… 3 (modulo 4) 3,7,11,15,19,23,27,… triangular 1,3,6,10,15,21,… perfect 6,28,496,… Fibonacci 1,1,2,3,5,8,13,21,…

Learn more by looking at Chapter 2

It is important to understand Number Theory to understand Encryption particularly Asymmetrical Encryption.

### FERMAT LITTLE THEOREM

**Fermat’s little theorem** states that if p is a

prime number

, then for any

integer

a, the number ap − a is an integer multiple of p. In the notation of

modular arithmetic

, this is expressed as:

For example, if a = 2 and p = 7, then 27 = 128, and 128 − 2 = 126 = 7 × 18 is an integer multiple of 7.

If a is not divisible by p, Fermat’s little theorem is equivalent to the statement that ap − 1 − 1 is an integer multiple of p, or in symbols:

[1]

[2]

For example, if a = 2 and p = 7, then 26 = 64, and 64 − 1 = 63 = 7 × 9 is thus a multiple of 7

Lavf55.33.100