Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

1 Answer 1

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

Your Answer

 
discard

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.