7.1 Euler’s Theorem
Recall that a multiplicative inverse for a class \([a]\in{\mathbb Z}_n\) is a class \([b]\in{\mathbb Z}_n\) such that \([a][b]=[1]\).
A class \([a]\in{\mathbb Z}_n\) is a unit if it has a multiplicative inverse in \({\mathbb Z}_n\). We let \(U_n\) denote the set of units in \({\mathbb Z}_n\).
We sometimes say that the integer \(a\) is a unit \(\text{mod}(n)\), meaning that \(ab\equiv 1\text{ mod }(n)\) for some integer \(b\).
\([a]\) is a unit in \({\mathbb Z}_n\) if and only if \(\gcd(a,n)=1\).
Proof. If \([a]\) is a unit then \(ab=1+qn\) for some integers \(b\) and \(q\); any common divisor of \(a\) and \(n\) would therefore divide \(1\), so \(\gcd(a,n)=1\).
Conversely, if \(\gcd(a,n)=1\) then \(1=au+nv\) for some \(u\) and \(v\) by Theorem 3.16, so \([u]\) is a multiplicative inverse of \([a]\).
- The units in \({\mathbb Z}_8\) are \([1], [3], [5]\) and \([7]\): in fact \([1][1]=[3][3]=[5][5]=[7][7]=[1]\), so each of these units is its own multiplicative inverse.
- In \({\mathbb Z}_9\), the units are \([1], [2], [4],[5], [7]\) and \([8]\): for instance \([2][5]=[1]\), so \([2]\) and \([5]\) are inverses of each other.
Thus \(U_8=\{[1], [3], [5], [7]\}\) and \(U_9=\{[1], [2], [4], [5], [7], [8]\}\).
Euler’s function
For any positive integer \(n\) we define \(\phi(n)=|U_n|\), the number of units in \({\mathbb Z}_n\).
By Lemma 7.1 \(\phi(n)\) is the number of integers \(a=1, 2, \ldots, n\) such that \(\gcd(a,n)=1\). This function \(\phi\) is called Euler’s function. It is easy to calculate \(\phi(n)\) for small \(n\). For example,
\[ \begin{array}{lccccccccccccccccccccc} n&=&1&2& 3& 4& 5& 6& 7& 8& 9& 10& 11& 12& 13 &14\cr \phi(n)&=&1& 1& 2& 2& 4& 2& 6& 4& 6& 4& 10& 4&&\cr \end{array} \]
Reduced sets of residues
We define a subset \(R\) of \(\mathbb Z\) to be a reduced set of residues \(\text{mod}(n)\) if it contains one element from each of the \(\phi(n)\) congruence classes in \(U_n\). For instance, \(\{ 1, 3, 5, 7\}\) and \(\{ \pm 1, \pm 3\}\) are both reduced sets of residues \(\text{mod}(8)\).
If \(R\) is a reduced set of residues \(\text{mod}(n)\), and if an integer \(a\) is a unit \(\text{mod}(n)\), then the set \(aR=\{ar\mid r\in R\}\) is also a reduced set of residues \(\text{mod}(n)\).
To see this note that for any \([r],[s]\in U_n\), \([a][r]=[a][s]\) if and only if \([r]=[s]\), and the inverse of \([a][r]\) is \([b][t]\) where \([b]\) is the inverse of \([a]\) and \([t]\) is the inverse of \([r]\).
If \(\gcd(a,n)=1\) then \(a^{\phi(n)}\equiv 1\text{ mod }(n)\).
Proof. Proof B of Theorem 6.4 can easily be adapted to this situation; we will merely outline the argument
We replace the integers \(1, 2, \ldots, p-1\) of Theorem 6.4 with a reduced set \(R=\{ r_1, r_2, \ldots, r_{\phi(n)}\}\) of residues \(\text{mod}(n)\).
If \(\gcd(a,n)=1\) then \(aR\) is also a reduced set of residues \(\text{mod}(n)\) so the product of all the elements of \(aR\) must be congruent to the product of all the elements of \(R\). This gives \(a^{\phi(n)}r_1r_2\ldots r_{\phi(n)}\equiv r_1r_2\ldots r_{\phi(n)}\), and since the factors \(r_i\) are all units they can be cancelled to give \(a^{\phi(n)}\equiv 1\).
Fermat’s Little Theorem is a special case of this result. If \(p\) is a prime, then by Lemma 7.1 the units in \({\mathbb Z}_p\) are the classes \([1], [2], \ldots, [p-1]\), so \(\phi(p)=p-1\) and hence \(a^{p-1}\equiv 1\text{ mod }(p)\).
If we take \(n=12\) then \(U_{12}=\{ \pm[1], \pm[5] \}\), and \(\phi(12)=4\); we have \((\pm 1)^4=1\) and \((\pm 5)^4=625\equiv 1\text{ mod }(12)\), so \(a^4\equiv 1\text{ mod }(12)\) for each \(a\) coprime to \(12\).
An interesting application of Euler’s Theorem is
If \(\gcd(a,n)=1\) then \(a^{\phi(n)-1}\) is an inverse of \(a\) modulo \(n\).
Proof. By Theorem 7.3 \[ a^{\phi(n)-1}a = a^{\phi(n)}\equiv\ 1\text{ mod }(n) \] and so \(a^{\phi(n)-1}\) is an inverse of \(a\text{ mod }(n)\).
The inverse of \(5\text{ mod }(12)\) is \(5^3 = 125\equiv 5\text{ mod }(12)\).