Why is Euler's Theorem true?  

Number Theory idea:  We consider the positive integers less than or equal to n which don't have any common factors with n, and multiply each of them by x modulo n.  Compare them to the same integers without multplying by x.

Example.

For n=15, consider x, 2x, 4x, 7x, 8x, 11x, 13x, 14x (mod 15), and compare them to 1, 2, 4, 7, 8, 11, 13, 14.  If we multiply all of the first set we get

and if we multiply all of the second set we get

What if we do all of this for x=11?  The first set will be

which is the same as the second set, only in a different order!  In fact, this always happens.  So

or

Next Section