Take the 2-minute tour ×

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.

share|improve this question
add comment

1 Answer

up vote 5 down vote accepted

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

share|improve this answer
Gerry Myerson:Yes,thanks. –  francis-jamet Dec 14 '11 at 15:50
@ Gerry: Do there exist examples of polynomials of above mentioned type which are not identically zero but have infinitely solutions? –  Nikhil Bellarykar Dec 16 '11 at 10:40
@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. –  Gerry Myerson Dec 17 '11 at 20:51
@GerryMyerson thanks for the clarification. Can you please give a link that describes the limits of $\phi(n)$ as given by you? –  Nikhil Bellarykar Dec 17 '11 at 21:03
@Nikhil, just type Euler phi into Google and go to the wikipedia article on the Euler totient function. –  Gerry Myerson Dec 18 '11 at 16:31
show 1 more comment

Your Answer


