# Prove for any given positive integer $N$ there exist only finitely many integers n with $φ(n)=N$ [duplicate]

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

How can I prove the above statement? Because Euler’s $φ$-function is bijection?

• Hint: Consider the prime factorization of $N$ and compute $\varphi(N)/N$. Jan 14, 2014 at 18:11
• Well, no: it is not a bijection, otherwise that you should prove. Jan 14, 2014 at 18:14

Let $$N$$ be a positive integer, $$p$$ be the least prime greater than $$N+1$$, and $$n$$ be any integer such that $$\varphi(n) = N$$. We now show that there are finitely many such $$n$$:

If $$q \geq p$$ is a prime divisor of $$n$$, then $$n = q^{k}m$$ for some $$k, m \geq 1$$ and $$gcd(q^{k}, m) = 1$$. Furthermore, $$\varphi (n) = \varphi (q^{k}) \varphi (m) \geq q-1$$ since $$\varphi (m) \geq 1$$ and $$\varphi (q^{k}) = q^{k-1}(q - 1) \geq q - 1$$. This leads us to a contradiction; for $$q-1 \geq p-1 \geq N$$. 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 $$\{p_1, p_2, .., p_m\}$$.

Now, consider the prime decomposition of $$n$$, $$p_1^{a_1}p_2^{a_2}...p_n^{a_n}$$, then $$\varphi(n) = \varphi(p_1^{a_1})\varphi(p_2^{a_2})...\varphi(p_m^{a_m})$$. Thus, we have $$\varphi(n) = \prod_{i = 1}^m p_i^{a_i-1}(p_i - 1)$$. Note that, if $$p^k$$ is a factor of $$n$$, then $$p^{k-1}$$ must be a factor of $$N$$, which ultimately limits the possible values for $$k$$. Therefore, $$n$$ must be a product of a bounded set of primes, each raised to a bounded exponent; there are finitely many such $$n$$.

Finally, for each positive integer $$N$$, there is a largest integer $$n$$ with $$\varphi(n) = N$$. Thus, as $$n$$ approaches infinity, so does $$\varphi(n)$$.

• I hope you'll find time to enlarge upon this link-only answer with a fuller explanation. Jan 14, 2014 at 18:16
• @hardmath why? The link contains a complete argument. Jan 14, 2014 at 18:17
• @vadim123 Why? It answers the question. Jan 14, 2014 at 18:17
• This link might be gone in a week but the question may last forever. Link-only answers are discouraged on Math.SE. If you don't want to summarize the link's solution, then you should leave the link as a comment. Jan 14, 2014 at 18:18
• @IgorRivin, on behalf of posterity I wish to give you my warmest upvote. Jan 14, 2014 at 18:31