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$.

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

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.

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.

**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}$.

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

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} $$

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

**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$.

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.

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.$

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)$

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.

**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.