Fermat's little theorem states that if p is a prime number, then for any integer a, the number a p − a is an integer multiple of p. In the notation of modular arithmetic, this is expressed as

a^{p} = a mod {p}

For example, if a = 2 and p = 7, 27 = 128, and 128 − 2 = 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 a p − 1 − 1 is an integer multiple of p:

a^{p-1} mod p = 1

Research Links

The quickest proof follows.  Take the series below:

 [a * 2a * 3a *4a * .... (p-1)a] mod p

= (a) mod p  * (2a) mod p * (3a) mod p * (4a) mod p  * .... (p-1)mod p   

Using an example of a=3 and p=17 is shown in the table below.  Note the jumble of all values 1 through (p-1) in column D.  All the values 1 through 16 are there once and only once just not in the order you are accustomed to.

So the value is equal to: 1*2*3*4*....*(p-1) = (p-1)!

= (a) mod p  * (2a) mod p * (3a) mod p * (4a) mod p  * .... (p-1)mod p = 1*2*3*4*....*(p-1) = (p-1)! 

= a^p  * (p-1)! mod p= (p-1)! mod p

= a^p mod p  = 1     It is in the above paragraph of mathematics that you can see that all the numbers 1,2,3....p-1 must be relatively prime to p in order for the derivation to work and the relation to hold.

Which leads to the interesting phrase

= (a^p-1) mod p  = 0   Below is an example of the values of this phrase with p=5

Fermat's Little Theorem Spreadsheet

Observation: Relationship of the Roots of the Polynomial

Using the example x^4-1 assuming p=5 you get the following root map:

x^4-1 = (x-1)(x-i)(x+1)(x+i) 

for x=2:

x^4-1 = (1)(2-i)(2+1)(2+i)=(1)(3)(5)= 15 and this relationship works for all the coprimes. 

for x=3:

x^4-1 = (2)(3-i)(3+1)(3+i)=(2)(4)(10)=80 

Categories: Math

0 Comments

Leave a Reply

Avatar placeholder

Your email address will not be published. Required fields are marked *