Algebra Solutions: At most finitely many integers have a given Euler totient

Prove that for any given positive integer $N$ there exist at most finitely many integers $n$ with $\varphi(n) = N$ , where $\varphi$ denotes the Euler totient function. Conclude in particular that $\varphi(n)$ tends to infinity as $n$ tends to infinity.

Let $N$ be a positive integer, and let $p$ be the least prime greater than $N+1$ . Let $n$ be an integer such that $\varphi(n) = N$ .
If $q \geq p$ is a prime divisor of $n$ , then $n = q^k \cdot m$ for some $k \geq 1$ and $m$ with $q$ not dividing $m$ . Then $\varphi(n) = \varphi(q^k) \cdot \varphi(m) \geq q-1 \geq p-1 > N$ , a contradiction. Thus no prime divisor of $n$ is greater than $N+1$ . In particular, the distinct prime divisors of $n$ belong to a finite set; say these primes are $p_1, p_2, \ldots, p_m$ .
Now we can write $n = p_1^{a_1} \cdot p_2^{a_2} \cdot \cdots \cdot p_m^{a_m}$ , for some $0 < a_i$ , and thus $\varphi(n) = \varphi(p_1^{a_1}) \cdot \varphi(p_2^{a_2}) \cdot \cdots \cdot \varphi(p_m^{a_m})$ . Thus we have $\varphi(n) = \Pi_{i=1}^m p_i^{a_i - 1}(p_i - 1)$ . Note that for each prime $p_i$ , $\varphi(n) \geq p_i^{a_i-1}(p_i - 1) > N$ for sufficiently large $a_i$ . Thus, for each $p_i$ , there are only finitely many permissible choices for the exponents $a_i$ . So the set of all $n$ with $\varphi(n) = N$ is a subset of a finite set hence finite.
Now for each positive integer $N$ , there is a largest integer $n$ with $\varphi(n) = N$ . Thus as $n$ approaches infinity, so does $\varphi(n)$ .

Algebra Solutions

At most finitely many integers have a given Euler totient

No comments:

Post a Comment