Proving $\phi(x) = n$ for natural values of $n$ has finite solutions

76 Views Asked by At

Question: Prove that for any given $n \in \mathbb N$, $\phi(x) = n$ has only finitely many solutions.

My attempt:

Let there be infinite solutions for

$$\phi(x) = n$$

so every natural number greater than $x$ has only $n$ primes before it. Thus, every number after the last prime is composite.

Now, let the finite set of primes be $p_1,p_2,...,p_n$.

Now, the number $p_1p_2...p_n + 1$ is relatively prime to all the finite primes, thus it is a new prime

This contradiction violates our assumption of a finite set of primes, so our assumption of infinite solutions is wrong.

Hence, $\phi(x) = n$ has only finite solutions.

Issue: I feel that the approach of $p_1p_2...p_n + 1$ is wrong and doesn't prove that the number itself is prime, but since it is of form $1 \text{ mod } p_i$ for $i \epsilon \text{ 1,2,...,n }$, thus it must be prime to all of them. Also, something about this proof feels off in terms of the assumptions. Any help is very appreciated!

PS: I know this is a duplicate but since I want to know what is wrong with my approach, I thought of sharing my method to get the explanation over the finite set of prime logic and the proof approach

1

There are 1 best solutions below

9
On BEST ANSWER

Edit: new answer due to change in OP question

Suppose $x$ has the following factorization: $$x = \prod_{p|n}p^{k_p}$$ Using the Euler's product formula, we have $$\phi(x) = \prod_{p|n}p^{k_p-1}(p-1)$$ Therefore $$\frac{\phi^2(x)}{x} = \prod_{p|n}p^{k_p-2}(p-1)^2 \geq \prod_{p|n}\frac{(p-1)^2}{p}$$

since $k_p \geq 1$. Notice that $\dfrac{(p-1)^2}{p} > 1$ for $p >2$, therefore: $$\frac{\phi^2(x)}{x} \geq \frac{1}{2} \Rightarrow \phi(x) \geq \sqrt{\frac{x}{2}}$$

If $\phi(x)=n$ then $n\geq\sqrt{\dfrac{x}{2}}$ therefore $x\leq2n^2$. Thus there can only be a finite number of solutions to $\phi(x) = n$