Exercise 0.2.10 ($\lim_{n o \infty} \varphi(n) = + \infty.$)

Question

Prove for any given positive integer $N$ there exist only finitely many integers $n$ with $\varphi(n) = N$ where $\varphi$ denotes Euler's $\varphi$-function. Conclude in particular that $\varphi(n)$ tends to infinity as $n$ tends to infinity.

Richard Ganaye · Accepted Answer

ewcommand{\Z}{\mathbb{Z}}

(See Ex. 2.3.39 in Niven.)
\begin{proof} 
 Let $x>1$ be a solution of $\varphi(x) = N$. Write $x = p_1^{a_1}\cdots p_k^{a_k},\ a_i>0$, the decomposition of $x$ in prime factors. Then
$$ N= \varphi(x) = p_1^{a_1-1}(p_1-1)\cdots p_k^{a_k-1}(p_k - 1).$$
Therefore $p_i - 1$ is a divisor of $N$. Since the set of divisors of $N$ is finite, there are only finitely many possible $p_i$. 

Write $N = q_1^{b_1} \cdots q_l^{b_l}$. If $a_i >1$, then $p_i^{a_i-1} \mid N$, so $p_i = q_j$ for some index $j$, and $a_i - 1 \leq b_j$, so $0 \leq a_i \leq b_j +1$, where $b_j$ is fixed, because $N$ is fixed. Thus there are only finitely possible exponents $a_i$. 

This proves that the equation $\varphi(x) = N$ has only a finite number of solution.

\bigskip
Let $A $ be any real number. By the preceding argument, their are only finitely many values of $n \in \Z^+$ such that $\varphi(n) \leq A$:
$$\{ n \in \Z^+ \mid \varphi(n) \leq A \} = \bigcup_{1 \leq i \leq \lfloor A floor} \{n\in \Z^+ \mid \varphi(n) = i\}$$
is a finite set.

So $ \{ n \in \Z^+ \mid \varphi(n) \leq A \} \subseteq [\![1, B]\!]$, where 
$$B = \max \, \{n \in \Z^+ \mid \varphi(n) \leq A\}$$
is a (finite)  integer. Hence if $n >B$, then $\varphi(n) >A$. This shows that
$$\forall A \in \R,\ \exists B \in \R,\ \forall n \in \Z^+,\ n >B \Rightarrow \varphi(n) >A,$$
so
$$\lim_{n 	o \infty} \varphi(n) = + \infty.$$
\end{proof}

Exercise 0.2.10 ($\lim_{n \to \infty} \varphi(n) = + \infty.$)

Answers

Comments

Exercise 0.2.10 ($\lim_{n \to \infty} \varphi(n) = + \infty.$)

Answers

Comments

Add answer