## At most finitely many integers have a given Euler totient

Prove that for any given positive integer there exist at most finitely many integers with , where denotes the Euler totient function. Conclude in particular that tends to infinity as tends to infinity.

Let be a positive integer, and let be the least prime greater than . Let be an integer such that .

If is a prime divisor of , then for some and with not dividing . Then , a contradiction. Thus no prime divisor of is greater than . In particular, the distinct prime divisors of belong to a finite set; say these primes are .

Now we can write , for some , and thus . Thus we have . Note that for each prime , for sufficiently large . Thus, for each , there are only finitely many permissible choices for the exponents . So the set of all with is a subset of a finite set hence finite.

Now for each positive integer , there is a largest integer with . Thus as approaches infinity, so does .

### Like this:

Like Loading...

*Related*

or leave a trackback:

Trackback URL.

## Comments

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!

Thanks!

The first problem can be fixed (I think) by making the 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 , there exists such that if , then . (1 always works, for example.) Moreover, this set is finite since it is bounded above by . Now let be the largest such for a given . This gives a function such that, if , then . Certainly if , then . Now I claim that for any , there exists such that the inequality is strict. Given , the set of all such that is finite, so there exists a natural number which is larger than all of these and such that is minimal. Then if , we have , and in fact by the minimalness of , . So is nondecreasing and its image is not bounded above. So (and this is where the confusion comes in) ‘tends to infinity’ as 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

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

Thanks again!

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.