Research Links

 

Eulers theorem is very similar to Fermat's little theorem.  It is not restricted to prime number p.  It is restricted to relatively prime a & p.  It states:

a^ {psi(p)} mod p = 1  

Where psi(p)    is the Euler totient function which is the number of integers less than and coprime to p.

Example:

    a=2      p = 15  

List of relative primes for   15 = [ 1, 2, 4, 7, 8, 11,13, 14 ]    thus    {psi(15)} = 8   

  2^8 mod(15)= 2^8 = 256 mod(15) =  1    

 

 If you followed the proof for Fermat's little theorem then you can understand this generalization rapidly.  As before when the integer a is coprime to p you get the jumble of all the integers 1,2,3…p-1.  This was guaranteed by p being prime in Fermat's little theorem.  When you relent on that condition then you have some integers a that are not coprime to p and they will not give you a full contingent of integers. See the spread sheet clips below

:  

2 is coprime to 15 and thus all values 0 through 14 are cycled through.  3 is not coprime to 15 and thus the gearing does not cycle through all values. 

In the spread sheet example clipped above the totient {psi(15)} = 8 

The following spread sheet snip contains the value of the modulus 1 to p-1 where p=15 in this case and the modulus of a*remainder.  As before with Fermat's little theorem the modulus values come in different order but contain identical values.

Thus:

m_1 * m_2 ...m_{psi(p)}  = am_1 * am_2 ...am_{psi(p)}  

m_1 * m_2 ...m_{psi(p)}  = a^{psi(p)}*[ m_1 * m_2 ...m_{psi(p)}]  mod p

a^{psi(p)} mod p  = 1

 

Above needs work.  See video derivation

Categories: Math

0 Comments

Leave a Reply

Avatar placeholder

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