7.2 Euler’s Product Formula
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 4.3, allows us to write any composite number as a product of prime powers. Theorem 7.10 will extend the information given in Lemma 7.8 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 7.9 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 7.8. 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 7.10 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 7.8 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 6 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 7.3 (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 7.13 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\).