Here I was trying to solve the question number 10, but I am unable to solve it.
I am sharing my thoughts when I was trying the problem.
I was trying to prove this statement by contradiction. So I assumed first that the number of solutions to this equation is infinite and then I tried to find a finite natural number, let us say 'A' which will be relatively prime to all those infinitely many solutions of that equation.
Now by Euler's theorem all those solutions of that equation will divide this particular integer: $$A^{\phi(x)} – 1.$$
$x$ is a solution to that equation and $\phi()$ is Euler's function.
Now as the number of solutions is infinite so it can be claimed that there are solutions which are infinitely large, since all the solutions belong to the set of natural numbers.
And then as all the solutions must divide this integer $A^{\phi(x)} – 1$ , this integer must be infinitely large which will be a contradiction to our assumption.
But I am unable to find such finite particular integer A which will do the work.
Please help me to know whether it is possible to find such A? If yes,then how?
And if no then how to solve the problem?
Best Answer
Yes, your idea can be made to work. Here is an argument. Assume that there are infinitely many solutions. One needs to get a contradiction. Note that the prime factors $p$ in $x$ cannot exceed $n+1$, otherwise $\phi(x)\geq \phi(p)=p-1>n$, showing that $x$ is not a solution. It suffices now to choose $A$ to be any prime number greater than $n+1$. Then $A$ is relatively prime to all the infinitely many solutions $x$. This gives a contradiction by the Euler's theorem as you mentioned. QED
Alternatively, a high-brow argument is to apply the following result (see reference herein): $$\phi(n)>\frac n{e^{\gamma}\log\log n+\frac 3{\log\log n}},~n>2,$$ where $\gamma$ is the Euler constant. The result follows, since the right hand side of the inequality goes to $\infty$ as $n$ goes to $\infty$.
Yet another proof: Just a sketch. As above the prime factors $p$ of $x$ cannot exceed $n+1$. By trivial estimate, the number of distinct prime factors of $x$ cannot exceed $\lfloor\log_2 n\rfloor+2$. Furthermore the exponent of a prime power cannot exceed $\lfloor\log_2 n\rfloor+1$. This shows that there are only finitely possibilities for $x$ with $\phi(x)=n$.