Chapter 6 Euler’s Function
In this short section, we consider one of the most important functions in number theory, namely Euler’s function \(\phi(n)\).
We shall study how to evaluate this function, its basic properties, and see how it can be applied to various problems such as the calculation of large powers and the design and implementation of cipher systems.
Although perhaps not immediately obvious, many of the results in Chapter 5 depended on the simple but important fact that if \(p\) is prime, and \(ab\equiv 0\text{ mod }(p)\), then \(a\equiv 0\) or \(b\equiv 0\text{ mod }(p)\). This makes the arithmetic of \({\mathbb Z}_p\) similar to that of \({\mathbb Z}\), in which the equation \(ab=0\) implies that \(a=0\) or \(b=0\). Unfortunately, this property fails when the modulus is composite. For example, if \(n=12\) then \(3\times4\equiv 0\text{ mod }(12)\) but \(3, 4\not\equiv 0\text{ mod }(12)\).
In Chapter 5 we proved Fermat’s Little Theorem, that if \(p\) is prime then \(a^{p-1}\equiv 1\text{ mod }(p)\) for all integers \(a\not\equiv 0\text{ mod }(p)\).
It would be useful if we had a similar result for composite moduli. However, if \(n=4\) and \(a=3\) then \(a^{n-1}=27\not\equiv 1\text{ mod }(4)\), so the result does not extend to composite values in a straightforward way.
We shall replace \(n-1\) with a different exponent \(e(n)\) such that \(a^{e(n)}\equiv 1\text{ mod }(n)\) for all \(a\) coprime to \(n\).
The simplest function with this property turns out to be Euler’s function \(\phi(n)\), one of the most important functions in number theory.
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\). We let \(U_n\) denote the set of units in \({\mathbb Z}_n\).
\([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 2.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 6.2 \(\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 5.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 5.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 6.2 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 6.4 \[ 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)\).
Calculating \(\phi(n)\)
Computing \(\phi(n)\) for small \(n\) is straightforward but we need to find a general formula for \(\phi(n)\). We have just seen that \(\phi(p)=p-1\) for all primes \(p\), and we now extend this to the case where \(n\) is a prime-power.
If \(n=p^e\) where \(p\) is prime, then \[\phi(n)=p^e-p^{e-1}=p^{e-1}(p-1)=n\Bigl(1-\frac{1}{ p}\Bigr)\,.\]
Proof. \(\phi(p^e)\) is the number of integers in \(\{ 1,\ldots, p^e\}\) which are coprime to \(p^e\), that is, not divisible by \(p\); this set has \(p^e\) members, of which \(p^e/p=p^{e-1}\) are multiples of \(p\), so \(\phi(p^e)=p^e-p^{e-1}=p^{e-1}(p-1).\)
Computing \(\phi(n)\) for composite \(n\)
The Fundamental Theorem of Arithmetic, Theorem 3.3, allows us to write any composite number as a product of prime powers. Theorem 6.11 will extend the information given in Lemma 6.9 to give a statement about \(\phi(n)\) valid for all integers \(n\).
First need the following technical result about complete sets of residues.
If \(A\) is a complete set of residues \(\text{mod }(n)\), and if \(m\) and \(c\) are integers with \(m\) coprime to \(n\), then the set \(Am+c=\{am+c\mid a\in A\}\) is also a complete set of residues \(\text{mod }(n)\).
Proof. If \(am+c\equiv a'm+c\) mod \((n)\), where \(a, a'\in A\), then by subtracting \(c\) and then cancelling the unit \(m\), we see that \(a\equiv a'\) mod \((n)\), and hence \(a=a'\). Thus the \(n\) elements \(am+c\;(a\in A)\) all lie in different congruence classes, so they form a complete set of residues mod \((n)\).
If \(m\) and \(n\) are coprime, then \(\phi(mn)=\phi(m)\phi(n)\).
Proof. We assume that \(m, n>1\), since the result is trivial if \(m=1\) or \(n=1\) (\(\phi(1)=1\)). We arrange the \(mn\) integers \(1, 2, \ldots, mn\) into a rectangular grid with \(n\) rows and \(m\) columns.
\[ \begin{array}{|c|c|c|c|c|} \hline \strut1&2&3&\ldots&m\cr \hline \strut m+1&m+2&m+3&\ldots&2m\cr \hline \strut\;\vdots&\;\vdots&\;\vdots&&\;\;\vdots\cr \hline \strut(n-1)m+1&(n-1)m+2&(n-1)m+3&\ldots&nm\cr \hline \end{array} \]
These integers \(1,\ldots, mn\) form a complete set of residues mod \((mn)\), so \(\phi(mn)\) is the number that are coprime to \(mn\). But this amounts to counting the number of these residues coprime to both \(m\) and \(n\).
Counting the entries mod \(m\)
The integers in a given column are all congruent \(\text{mod}(m)\), and the \(m\) columns correspond to the \(m\) congruence classes \(\text{mod}(m)\). Hence exactly \(\phi(m)\) of the columns consist of integers \(i\) coprime to \(m\), and the other columns consist of integers with \(\gcd(i,m)>1\).
Counting them mod \(n\)
Now each column of integers coprime to \(m\) has the form \(c, m+c, 2m+c, \ldots, (n-1)m+c\) for some \(c\). By Lemma 6.10 this is a complete set of residues \(\text{mod}(n)\), since \(A=\{0, 1, 2, \ldots, n-1\}\) is and since \(\gcd(m,n)=1\). Such a column therefore contains \(\phi(n)\) integers coprime to \(n\), then these \(\phi(m)\) columns yield \(\phi(m)\phi(n)\) integers \(i\) coprime to both \(m\) and \(n\). Thus \(\phi(mn)=\phi(m)\phi(n)\), as required.
The integers \(m=3\) and \(n=4\) are coprime, with \(\phi(3)=\phi(4)=2\); here \(mn=12\) and \(\phi(12)=2.2=4\).
Form the array in the above proof with \(m=5\) and \(n=4\); by finding the entries coprime to \(20\), verify that \(\phi(20)=\phi(5)\phi(4)\).
If \(n\) has prime-power factorisation \(n=p_1^{e_1}\ldots p_k^{e_k}\) then \[\phi(n)=\prod_{i=1}^k\phi(p_i^{e_i}) =\prod_{i=1}^k(p_i^{e_i}-p_i^{e_i-1})=n\prod_{i=1}^k\Bigl(1-\frac{1}{p_i}\Bigr)\,.\]
Proof. We prove the first expression by induction on \(k\), the other expressions then follow easily.
For the anchoring step with \(k=1\) we use Lemma 6.9. Now assume that \(k>1\) and that the result is true for all integers divisible by fewer than \(k\) primes.
We have \(n=p_1^{e_1}\ldots p_{k-1}^{e_{k-1}}.p_k^{e_k}\), where \(p_1^{e_1}\ldots p_{k-1}^{e_{k-1}}\) and \(p_k^{e_k}\) are coprime, so Theorem 6.11 gives \[\phi(n)=\phi(p_1^{e_1}\ldots p_{k-1}^{e_{k-1}})\phi(p_k^{e_k})\,.\]
The induction hypothesis gives \[\phi(p_1^{e_1}\ldots p_{k-1}^{e_{k-1}})=\prod_{i=1}^{k-1}(p_i^{e_i}-p_i^{e_i-1})\,,\]
Now Lemma 6.9 gives \[\phi(p_k^{e_k})=(p_k^{e_k}-p_k^{e_k-1})\,,\] so by combining these two results we get \[\phi(n)=\prod_{i=1}^k(p_i^{e_i}-p_i^{e_i-1})\,.\]
An alternative form of the result
We often express this result more concisely using the notation \(\phi(n)=n\prod\limits_{p|n}(1-\frac{1}{p})\), where \(\prod\limits_{p|n}\) denotes the product over all primes \(p\) dividing \(n\).
Calculate \(\phi(60)\).
The primes dividing \(60\) are \(2, 3\) and \(5\), so \[\phi(60)=60\Bigl(1-\frac{1}{2}\Bigr)\Bigl(1-\frac{1}{3}\Bigr)\Bigl(1-\frac{1}{5}\Bigr)=60.\frac{1}{2}.\frac{2}{3}.\frac{4}{5}=16\,.\] We can confirm this by writing down the integers \(i=1, 2, \ldots, 60\), and then deleting those with \(\gcd(i,60)>1\).
Calculate \(\phi(42)\), and confirm it by finding a reduced set of residues \(\text{mod}(42)\).
For which values of \(n\) is \(\phi(n)\) odd? Show that there are integers \(n\) with \(\phi(n)=2,4,6,8,10\) and \(12\), but not \(14\).
Show that for each integer \(m\), there are only finitely many integers \(n\) such that \(\phi(n)=m\).
Find the smallest integer \(n\) such that \(\phi(n)/n<1/4\).
Applications of Euler’s function
Having seen how to calculate Euler’s function \(\phi(n)\), we now look for some applications of it. We saw in Chapter 5 how to use Fermat’s Little Theorem \(a^{p-1}\equiv 1\) to simplify congruences \(\text{mod}(p)\), where \(p\) is prime, and we can now make similar use of Euler’s Theorem \(a^{\phi(n)}\equiv 1\) to simplify congruences \(\text{mod}(n)\) when \(n\) is composite.
Find the last two decimal digits of \(3^{1492}\).
This is equivalent to finding the least non-negative residue of \(3^{1492}\text{ mod }(100)\).
Now \(3\) is coprime to \(100\), so Theorem 6.4 (with \(a=3\) and \(n=100\)) gives \(3^{\phi(100)}\equiv 1\text{ mod }(100)\). The primes dividing \(100\) are \(2\) and \(5\), so Corollary 6.14 gives \(\phi(100)=100.(1/2).(4/5)=40\), and hence we have \(3^{40}\equiv 1\text{ mod }(100)\). Since \(1492\equiv 12\text{ mod }(40)\), it follows that \(3^{1492}\equiv 3^{12}\) mod \((100)\). Now \(3^4=81\equiv-19\text{ mod }(100)\), so \(3^8\equiv(-19)^2=361\equiv-39\) and hence \(3^{12}\equiv-19.-39=741\equiv 41\). The last two digits are therefore \(41\).
Show that if a positive integer \(a\) is coprime to \(10\), then the last three decimal digits of \(a^{2001}\) are the same as those of \(a\).