Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|improve this question
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|cite|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? – NikBels 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? – NikBels 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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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