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

• Anonymous  On October 17, 2011 at 8:44 am

Hey there,

This is a great proof and I wouldn’t have come up with it on my own. My instinct was to assume that there are infinitely many and come up with a contradiction, but I wasn’t able to do it. I just see a couple problems with your proof. I’ll try to explain it here without having LaTeX to help me out with the notation.🙂

In the second line of the third paragraph of your proof when you’ve taken \phi(n), the exponent on p_i doesn’t work. You’ve already allowed the possibility that some of your a_i could be 0, and if that’s the case then you certainly don’t want to have a_i-1 when you find \phi(n). Instead of writing your exponent as a_i-1, I would suggest saying \max\{0,a_i-1\}. That way if your a_i was 0, it will stay 0 when you find \phi(n) instead of going to -1.

The second problem is a little more serious. Your explanation that \phi(n) approaches infinity is wrong. It’s true that for any given N, there is a largest n such that \phi(n)=N, but that doesn’t mean that the n’s go to infinity. It actually doesn’t even mean that the n’s are increasing everywhere, but even if you could prove that, there are several sequences that are increasing everywhere that converge (e.g. arctangent(x)).

What you probably have to do here is show that \phi(n) is always greater than or equal to another sequence you already know goes to infinity. I found a paper here that shows \phi(n) \ge \sqrt{n}:

I had to fill in some gaps in the proof, but overall I didn’t think it was too difficult to follow.

Thanks for posting this proof, and good luck with your algebra studies!

• nbloomf  On October 17, 2011 at 9:23 am

Thanks!

The first problem can be fixed (I think) by making the $a_i$ strictly positive, which is what we want anyway.

As to the second problem, I will be the first to admit having some confusion about what is meant by ‘tends to infinity’. (My analytical intuition is laughably weak.) I’m fairly sure that with this argument in hand, we can say the following.

For every $N$, there exists $P$ such that if $n \geq N$, then $\varphi(n) \geq P$. (1 always works, for example.) Moreover, this set is finite since it is bounded above by $\varphi(N)+1$. Now let $P_N$ be the largest such $P$ for a given $N$. This gives a function $P : \mathbb{N} \rightarrow \mathbb{N}$ such that, if $n \geq N$, then $\varphi(n) \geq P_N$. Certainly if $M \geq N$, then $P_M \geq P_N$. Now I claim that for any $N$, there exists $M$ such that the inequality $P_M \geq P_N$ is strict. Given $N$, the set of all $n$ such that $\varphi(n) \leq P_N$ is finite, so there exists a natural number $M$ which is larger than all of these and such that $P_M - P_N$ is minimal. Then if $n \geq M$, we have $\varphi(n) > P_N$, and in fact by the minimalness of $M$, $\varphi(n) \geq P_M$. So $P$ is nondecreasing and its image is not bounded above. So (and this is where the confusion comes in) $P_N$ ‘tends to infinity’ as $N$ tends to infinity.

One difference here with the real number situation is that the naturals are discrete, so any strictly increasing sequence is unbounded and every subset has a least element.

This could be completely wrong, though.

By the way- to use Latex in the comments just put the markup in between

$latex$

. So $latex ax^2 + bx + c$ becomes $ax^2 + bx + c$.

Thanks again!

• Anonymous  On October 17, 2011 at 8:58 am

Ack – sorry for the double comment. I just realized that my idea of using \max on the exponent doesn’t work, because you still might have a factor of p_i-1 in there that you don’t want. I think to fix this you need to say something like “assume n=\prodp_i^{a_i} for some 1\ge i\ge m with a_i \ge 1” and go from there.