Euler's Theorem

Euler's Theorem - Any number a relatively prime to m there exists the congruence a^(m) = 1 mod(m)

Where (m) equals Euler's Totient Function.

Proof:

Let r₁, r₂, r₂, . . . , r_(m) equal the remainders less than and relatively prime to m.
Multiply each remainder by a and divide by m.

r_ia = q_im + r_i'

Where r_i' is a positive integer less than m
r_i' is then relatively prime to m because any common factor of q_im and r_i', would be a factor of r_ia.

r_ia = r_i' mod(m)

Two different remainders r_i and r_j cannot have the same congruence.

Therefore, r_i and r_i' run through the same set of remainders.

Example:

Let m = 12 , a = 5

(12) = 4, Numbers less than m that are relatively prime to m: 1, 5, 7, 11

Multiply all remainders by a = 5 and congruence mod(m = 12)

1a	=	5	mod(12)
5a	=	1	mod(12)
7a	=	11	mod(12)
11a	=	7	mod(12)

Multiplying all congruences together:

a4(1)(5)(7)(11)	=	(5)(1)(11)(7) mod(m)
a4	=	1 mod(m)
a(m)	=	1 mod(m)