Eulers Theorem

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.