TAOCP 1.2.4 Exercise 30
Let $n$ be a positive integer and let $\varphi(n)$ denote the number of integers in ${0,1,\ldots,n-1}$ that are relatively prime to $n$, as in exercise 27.
Section 1.2.4: Integer Functions and Elementary Number Theory
Exercise 30. [M30] Prove that the function $\varphi(n)$ of exercise 27 is multiplicative. Using this fact, evaluate $\varphi(1000000)$, and give a method for evaluating $\varphi(n)$ in a simple way once $n$ has been factored into primes.
Verified: yes
Solve time: 36s
Setup
Let $n$ be a positive integer and let $\varphi(n)$ denote the number of integers in ${0,1,\ldots,n-1}$ that are relatively prime to $n$, as in exercise 27. We are asked to prove that $\varphi$ is multiplicative, that is,
$$ \varphi(rs) = \varphi(r)\varphi(s) \quad \text{whenever } r \perp s, $$
and then to evaluate $\varphi(10^6)$ and describe a method for computing $\varphi(n)$ once the prime factorization of $n$ is known.
We recall that $x \perp y$ means $\gcd(x,y)=1$, and that if $r \perp s$, then any integer $a$ is relatively prime to $rs$ if and only if $a$ is relatively prime to both $r$ and $s$.
Solution
Let $r$ and $s$ be positive integers with $r \perp s$. Consider the set
$$ S = {0,1,2,\ldots, rs-1}. $$
We aim to count the number of elements of $S$ that are relatively prime to $rs$, that is, $\varphi(rs)$.
Write any integer $a \in S$ uniquely as
$$ a = x + ry, \quad 0 \le x \le r-1, \quad 0 \le y \le s-1, $$
so that $x = a \bmod r$ and $y = \lfloor a/r \rfloor$.
Then $a \perp r$ if and only if $x \perp r$, and $a \perp s$ if and only if $x + ry \perp s$.
Since $r \perp s$, the map $y \mapsto x + ry \pmod s$ is bijective for each fixed $x$. Indeed, if $x + ry_1 \equiv x + ry_2 \pmod s$, then $r(y_1 - y_2) \equiv 0 \pmod s$, and $r \perp s$ implies $y_1 - y_2 \equiv 0 \pmod s$, which forces $y_1 = y_2$ in $0 \le y_1, y_2 \le s-1$.
Therefore, for a fixed $x \perp r$, there are exactly $\varphi(s)$ values of $y$ such that $a = x + ry \perp s$, and hence $a \perp rs$.
There are $\varphi(r)$ choices for $x \in {0,\ldots,r-1}$ with $x \perp r$, so by the bijection above, the total number of integers $a \in S$ with $a \perp rs$ is
$$ \varphi(rs) = \varphi(r)\varphi(s). $$
This proves that $\varphi$ is multiplicative.
Next, we evaluate $\varphi(10^6)$. Write $10^6 = 2^6 \cdot 5^6$. Since $2$ and $5$ are prime, we have
$$ \varphi(2^6) = 2^6 - 2^5 = 64 - 32 = 32, \quad \varphi(5^6) = 5^6 - 5^5 = 15625 - 3125 = 12500. $$
Using multiplicativity,
$$ \varphi(10^6) = \varphi(2^6) \varphi(5^6) = 32 \cdot 12500 = 400000. $$
Finally, once the prime factorization
$$ n = \prod_{i=1}^k p_i^{e_i} $$
is known, the multiplicativity of $\varphi$ and the formula $\varphi(p^e) = p^e - p^{e-1} = p^e (1 - 1/p)$ for prime powers yield
$$ \varphi(n) = \prod_{i=1}^k \varphi(p_i^{e_i}) = \prod_{i=1}^k p_i^{e_i} \left(1 - \frac{1}{p_i}\right) = n \prod_{i=1}^k \left(1 - \frac{1}{p_i}\right). $$
This gives a simple and general method for evaluating $\varphi(n)$ once $n$ is factored into primes.
Verification
Check the evaluation of $\varphi(10^6)$ step by step:
- $\varphi(2^6) = 64 - 32 = 32$
- $\varphi(5^6) = 15625 - 3125 = 12500$
- $\varphi(10^6) = 32 \cdot 12500 = 400000$
The multiplicativity argument is correct: the bijection $y \mapsto x + ry \pmod s$ holds because $\gcd(r,s)=1$, and each $x \perp r$ yields $\varphi(s)$ values of $y$.
Notes
This method extends to any positive integer $n$. Once $n = \prod p_i^{e_i}$ is known, each factor $\varphi(p_i^{e_i}) = p_i^{e_i} - p_i^{e_i-1}$, and multiplicativity gives $\varphi(n)$. Alternative proofs of multiplicativity can use the Chinese Remainder Theorem, yielding the same formula.
This completes the proof.
∎
$$ \boxed{\varphi(10^6) = 400000} $$