Sooji Shin

Fermat's Little Theorem says:

Theorem 1 (Fermat)  If p is a prime number and (a, p)=1, that is a and p are relatively primes, then a^p-1 ≡ 1 (mod p).

Euler gave a generalization of Fermat's theorem. His generalization will follow at once from next theorem, which is proceed by counting, using essentially the same argument as in finite integral domain. (See 69th and 70th articles.)

Lemma 2.  The set G_n of nonzero elements of Z_n that are not zero divisors forms a group under multiplication mudulo n.

Proof.  First we must show that G_n is closed under multiplication modulo n. Let a, b∈G_n. If ab is not in G_n, then there would exist c in Z_n such that c≠0 and (ab)c=0. Now (ab)c=0 implies that a(bc)=0. Since b∈G_n and c≠0, we have bc≠0 by definition of G_n. But then a(bc)=0 would imply that a not in G_n contrary to assumption. Note that we have shown that for any ring the set of elements that are not zero divisors is closed under multiplication. No structure of Z_n other than ring structure has been involved so far.
We now show that G_n is a group. Of course, multiplication modulo n is associative, and 1∈G_n. It remains to show that for a∈G_n, there is b∈G_n such that ab=1. Let 1, a₁, a₂, …, a_r be the elements of G_n. The elements a1, aa₁, aa₂, …, aa_r are all different, for if aa_i=aa_j, then a(a_i-a_j)=0, and since a∈G_n and thus is not a zero divisor, we must have a_i-a_j=0 or a_i=a_j. Therefore by counting, we find that either a1=1, or some aa_i must be 1, so a has a multiplicative inverse.  QED.

Let n be a positive integer. Let φ(n) be defined as the number of positive integers less than or equal to n and relatively prime to n. Note that φ(1)=1. For the zero divisors are precisely those nonzero elements that are not relatively prime to n in the ring Z_n, φ(n) us the number of nonzero elements of Z_n that are not zero divisors. This function φ is the Euler phi-function. We can now describe Euler's generalization of Fermat's theorem.

Theorem 3 (Euler)  If a is an integer relatively prime to n, then a^φ(n)-1 is divisible by n, that is, a^φ(n) ≡ 1 (mod n).

Proof.  If a is relatively prime to n, then the coset a+nZ containing a contains an integer b<n an relatively prime to n. Using the fact that multiplication of these cosets by multiplication modulo n of representatives is well-defined, we have a^φ(n)≡b^φ(n) (mod n). But by Lemma, b can be viewed as an element of the multiplicative group G_n of order φ(n) consisting of the φ(n) elements of Z_n relatively prime to n. Thus b^φ(n) ≡ 1 (mod n).  QED.

Reference
John B. Fraleigh, A First Course in Abstract Algebra 7ed, Addison-Wesley

Geschrieben von Sooji Shin