Fermat's Little Theorem says:

Theorem 1. (Fermat) If \(p\) is a prime number and \((a,~p)=1,\) that is, if \(a\) and \(p\) are relatively primes, then \(a^{p-1}\equiv 1\) \(({\rm 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.

Lemma 2. The set \(G_n\) of nonzero elements of \(\mathbb{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\in G_n.\) If \(ab\) were not in \(G_n ,\) then there would exist \(c \in \mathbb{Z}_n \) such that \(c \ne 0\) and \((ab)c=0.\) Now \((ab)c=0\) implies that \(a(bc)=0.\) Since \(b\in G_n \) and \(c\ne 0,\) we have \(bc\ne 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 \(\mathbb{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\in G_n\). It remains to show that for \(a\in G_n ,\) there is \(b\in G_n\) such that \(ab=1.\) Let \(1,\) \(a_1,\) \(a_2,\) \(\cdots ,\) \(a_r\) be the elements of \(G_n\). The elements \(a1,\) \(aa_1 ,\) \(aa_2 ,\) \(\cdots ,\) \(aa_r \) are all different, for if \(aa_i = aa_j ,\) then \(a(a_i - a_j )=0,\) and since \(a\in 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.

Let \(n\) be a positive integer. Let \(\phi (n)\) be defined as the number of positive integers less than or equal to \(n\) and relatively prime to \(n.\) Note that \(\phi (1)=1.\) For the zero divisors are precisely those nonzero elements that are not relatively prime to \(n\) in the ring \(\mathbb{Z}_n\), \(\phi (n)\) is the number of nonzero elements of \(\mathbb{Z}_n\) that are not zero divisors. This function \(\phi\) 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^{\phi (n)-1}\) is divisible by \(n\), that is, \(a^{\phi (n)} \equiv 1\) \(({\rm mod}~n).\)

Proof. If \(a\) is relatively prime to \(n\), then the coset \(a+n\mathbb{Z}\) containing \(a\) contains an integer \(b < n\) which is relatively prime to \(n\). Using the fact that multiplication of these cosets by multiplication modulo \(n\) of representatives is well-defined, we have \(a^{\phi (n)} \equiv b^{\phi (n)}\) \(({\rm mod}~n).\) But by Lemma, \(b\) can be regarded as an element of the multiplicative group \(G_n\) of order \(\phi (n)\) consisting of the \(\phi (n)\) elements of \(\mathbb{Z}_n\) relatively prime to \(n.\) Thus \(b^{\phi (n)} \equiv 1\) \(({\rm mod}~n).\)