If $n$ is a positive integer, let $\phi(n)$ the Euler function.

( if $n=p_1^{\alpha_1}\dots p_k^{\alpha_k}$ with $p_i$ distinct primes, we have $\phi(n)=p_1^{\alpha_1-1} \dots p_k^{\alpha_k-1}(p_1-1)\dots(p_k-1)$ )

Let $P$ a polynomial in $\mathbb{Z}[X,Y]$.

We suppose there exists an infinite number of positive integer $n$ such that $P(n,\phi(n))=0$

Is $P$ reducible in factors of degree one ?

Thanks in advance.


If $p(x,y)=(x-y)^2-x$, then $p(q^2,\phi(q^2))=0$ for all primes $q$.

  • $\begingroup$ Gerry Myerson:Yes,thanks. $\endgroup$ – francis-jamet Dec 14 '11 at 15:50
  • $\begingroup$ @ Gerry: Do there exist examples of polynomials of above mentioned type which are not identically zero but have infinitely solutions? $\endgroup$ – nb1 Dec 16 '11 at 10:40
  • $\begingroup$ @Nikhil, I don't know. $\phi(n)$ is (in some sense) generally between $n^{1-\epsilon}$ and $n/\log\log n$ which makes it difficult for polynomial relations to hold without holding identically, but I don't see offhand how to turn this observation into a proof of anything. $\endgroup$ – Gerry Myerson Dec 17 '11 at 20:51
  • $\begingroup$ @GerryMyerson thanks for the clarification. Can you please give a link that describes the limits of $\phi(n)$ as given by you? $\endgroup$ – nb1 Dec 17 '11 at 21:03
  • $\begingroup$ @Nikhil, just type Euler phi into Google and go to the wikipedia article on the Euler totient function. $\endgroup$ – Gerry Myerson Dec 18 '11 at 16:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.