3.8 The Euler Phi Function

When something is known about $\Z_n$, it is frequently fruitful to ask whether something comparable applies to $\U_n$. Here we look at $\U_n$ in the context of the previous section. To aid the investigation, we introduce a new quantity, the Euler phi function, written $\phi (n)$, for positive integers $n$.

Definition 3.8.1 $\phi (n)$ is the number of non-negative integers less than $n$ that are relatively prime to $n$. In other words, if $n>1$ then $\phi (n)$ is the number of elements in $\U_n$, and $\phi(1)=1$. $\square$

Example 3.8.2 You can verify readily that $\phi (2)=1$, $\phi (4)=2$, $\phi (12)=4$ and $\phi (15)=8$. $\square$

Example 3.8.3 If $p$ is a prime, then $\phi (p)=p-1$, because $1$, $2$, …, $p-1$ are all relatively prime to $p$, and $0$ is not. $\square$

For any number $n$, $\phi(n)$ turns out to have a remarkably simple form; that is, there is a simple formula that gives the value of $\phi(n)$. We've already seen how simple it is for primes. As is typical of many results in number theory, we will work our way gradually to any $n$, looking next at powers of a single prime.

Theorem 3.8.4 If $p$ is a prime and $a$ is a positive integer, then $$ \phi (p^a)=p^a-p^{a-1} $$

Proof. We want to calculate the number of non-negative integers less than $n=p^a$ that are relatively prime to $n$. As in many cases, it turns out to be easier to calculate the number that are not relatively prime to $n$, and subtract from the total. List the non-negative integers less than $p^a$: $0$, $1$, $2$, …, $p^a-1$; there are $p^a$ of them. The numbers that have a common factor with $p^a$ (namely, the ones that are not relatively prime to $n$) are the multiples of $p$: $0$, $p$, $2p$, …, that is, every $p$th number. There are thus $p^a/p=p^{a-1}$ numbers in this list, so $\phi(p^a)=p^a-p^{a-1}$.$\qed$

Example 3.8.5 $\phi (32)=32-16=16$, $\phi (125)=125-25=100$. $\square$

Now we want to extend our formula to handle any positive integer $n$. Consider an example first:

Example 3.8.6 Since $$ \eqalign{ \U_{20}&=\{[1],[3],[7],[9],[11],[13],[17], [19]\},\cr \U_{4}& =\{[1],[3]\},\cr \U_{5}& =\{[1],[2],[3],[4]\},\cr} $$ both $\U_{20}$ and $\U_4\times \U_5$ have 8 elements. In fact, the correspondence discussed in the Chinese Remainder Theorem between $\Z_{20}$ and $\Z_{4}\times \Z_5$ is also a 1-1 correspondence between $\U_{20}$ and $\U_4\times \U_5$: $$ \matrix{ [1]&\leftrightarrow&([1],[1])&\quad&[11]&\leftrightarrow& ([3],[1])\cr [3]&\leftrightarrow&([3],[3])&\quad&[13]&\leftrightarrow& ([1],[3])\cr [7]&\leftrightarrow&([3],[2])&\quad&[17]&\leftrightarrow& ([1],[2])\cr [9]&\leftrightarrow&([1],[4])&\quad&[19]&\leftrightarrow& ([3],[4])\cr} $$ $\square$

Using the Chinese Remainder Theorem we can prove that this is true in general.

Theorem 3.8.7 If $a$ and $b$ are relatively prime and $n=ab$, then $\phi (n)=\phi (a)\phi (b)$.

Proof. We want to prove that $|\U_n|=|\U_a|\cdot|\U_b|$. As indicated in the example, we will actually prove more, by exhibiting a one to one correspondence between the elements of $\U_n$ and $\U_a\times\U_b$. We already have a one to one correspondence between the elements of $\Z_n$ and $\Z_a\times\Z_b$. Again as indicated by the example, we just have to prove that this same correspondence works for $\U_n$ and $\U_a\times\U_b$. That is, we already know how to associate any $[x]$ with a pair $([x],[x])$; we just need to know that $[x]\in \U_n$ if and only if $([x],[x])\in\U_a\times\U_b$. After a long-winded build up, here's the proof: $[x]$ is in $\U_n$ if and only if $(x,n)=1$ if and only if $(x,a)=1$ and $(x,b)=1$ if and only if $([x],[x])\in \U_a\times \U_b$.$\qed$

Corollary 3.8.8 Suppose $n=ab$, with $a$ and $b$ relatively prime. For $x=0,1,…, n-1$, if $[x]\in \U_{n}$, associate $[x]$ with $([x], [x])\in \Z_a\times \Z_b$. This gives a one-to-one correspondence between $\U_n$ and $\U_a\times \U_b$.

Proof. We proved this already in the proof of the previous theorem, but it deserves its own statement.$\qed$

Now we know enough to compute $\phi(n)$ for any $n$.

Example 3.8.9 $\phi (200)=\phi(25)\phi(8)=(25-5)(8-4)=80.$ $\square$

Example 3.8.10 $\displaystyle\phi (2^33^47^2)=\phi(2^3)\phi (3^47^2) =\phi (2^3)\phi (3^4)\phi(7^2)=(2^3-2^2)(3^4-3^3)(7^2-7)$ $\square$

We can express this as a formula once and for all:

Theorem 3.8.11 If $n$ is a positive integer with prime factorization $p_1^{e_1}p_2^{e_2}\cdots p_k^{e_k}$, then $$ \phi (n)= (p_1^{e_1}-p_1^{e_1-1}) (p_2^{e_2}-p_2^{e_2-1})\cdots (p_k^{e_k}-p_k^{e_k-1}). $$

Proof. The proof by induction is left as an exercise.$\qed$

Leonhard Euler. Euler (pronounced "oiler'') was born in Basel in 1707 and died in 1783, following a life of stunningly prolific mathematical work. His complete bibliography runs to nearly 900 entries; his research amounted to some 800 pages a year over the whole of his career. He continued doing research right up until his sudden death while relaxing with a cup of tea. For almost all of the last 17 years of his life he was totally blind.

The breadth of Euler's knowledge may be as impressive as the depth of his mathematical work. He had a great facility with languages, and studied theology, medicine, astronomy and physics. His first appointment was in medicine at the recently established St. Petersburg Academy. On the day that he arrived in Russia, the academy's patron, Catherine I, died, and the academy itself just managed to survive the transfer of power to the new regime. In the process, Euler ended up in the chair of natural philosophy instead of medicine.

Euler is best remembered for his contributions to analysis and number theory, especially for his use of infinite processes of various kinds (infinite sums and products, continued fractions), and for establishing much of the modern notation of mathematics. Euler originated the use of $e$ for the base of the natural logarithms and $i$ for $\sqrt{-1}$; the symbol $\pi$ has been found in a book published in 1706, but it was Euler's adoption of the symbol, in 1737, that made it standard. He was also responsible for the use of $\sum$ to represent a sum, and for the modern notation for a function, $f(x)$.

Euler's greatest contribution to mathematics was the development of techniques for dealing with infinite operations. In the process, he established what has ever since been called the field of analysis, which includes and extends the differential and integral calculus of Newton and Leibniz. For example, by treating the familiar functions $\sin x$, $\cos x$ and $e^x$ analytically (as infinite series), Euler could easily establish identities that became fundamental tools in analysis. One such is the well-known $ e^{ix}=\cos x + i\sin x$; substituting $x=\pi$ gives $e^{i\pi}=-1$ or $e^{i\pi}+1=0$, a remarkable equation containing perhaps the five most important constants in analysis.

Euler used infinite series to establish and exploit some remarkable connections between analysis and number theory. Many talented mathematicians before Euler had failed to discover the value of the sum of the reciprocals of the squares: $1^{-2}+2^{-2}+3^{-2}+\cdots$. Using the infinite series for $\sin x$, and assuming that it behaved like a finite polynomial, Euler showed that the sum is $\pi^2/6$. Euler's uncritical application of ordinary algebra to infinite series occasionally led him into trouble, but his results were overwhelmingly correct, and were later justified by more careful techniques as the need for increased rigor in mathematical arguments became apparent. We'll see Euler's name more than once in the remainder of the chapter.

The information here is taken from A History of Mathematics, by Carl Boyer, New York: John Wiley & Sons, 1968.

Exercises 3.8

Ex 3.8.1 Construct the correspondence between

a) $\U_{21}$ and $\U_{3}\times \U_{7}$

b) $\U_{30}$ and $\U_{5}\times \U_{6}$

Ex 3.8.2 Given the following values of $a$, $b$ and the element $([y],[z])$ of $\U_a\times \U_b$, use the Euclidean Algorithm to find the corresponding element of $\U_n$.

a) $a=7$, $b= 11$, $([4], [9])$

b) $a= 12$, $b= 17$, $([11],[2])$

Ex 3.8.3 Compute the following:

a) $\phi (512)$

b) $\phi (9,000)$

c) $\phi ( 2^3\cdot 5^2\cdot 7^5\cdot 11^3)$

Ex 3.8.4 Suppose in the correspondence between $\U_{175}$ and $\U_{25}\times \U_7$ that $[x]$ corresponds to $([13], [2])$. What does $[x]^2$ correspond to? What does $[x]^{-1}$ correspond to?

Ex 3.8.5 The divisors of $6$ are $1$, $2$, $3$, $6$. Observe that $$ \phi (1)+\phi (2)+\phi (3)+\phi (6)= 1 + 1 + 2 + 2 = 6. $$ Perform a similar computation with $6$ replaced by $10$.

Ex 3.8.6 Find all $a$ such that $\phi (a)=6$.

Ex 3.8.7 If $a|b$, prove $\phi (a)|\phi (b)$.

Ex 3.8.8 What primes can be expressed in the form $\phi (n)$ for some $n$?

Ex 3.8.9 Prove that $\displaystyle\phi(n)=n\prod_{p|n}\big(1-{1\over p}\big)$; the product is over all primes $p$ that divide $n$.

Ex 3.8.10 Prove Theorem 3.8.11.

Ex 3.8.11 Find all $n$ such that $\phi(n)$ is odd, and prove that you have found all such $n$.

Ex 3.8.12 In the proof of theorem 3.8.7, we claimed that if $n=ab$ then $(x,n)=1$ if and only if $(x,a)=1$ and $(x,b)=1$. Prove this.