20091006, 01:45  #1 
Jan 2005
Transdniestr
503 Posts 
Phi Question
I was wondering if there's a conjecture or proven theorem for the following:
For every integer m > 1, there exists a positive integer n, such that are exactly m different positive integers x such that phi(x) = n.  I was fiddling around with something and found that this is true through m=32 (hardly proof of anything of course) but I was just curious. Edit: To be clear, by the phi function, I mean Euler's phi or totient function. Last fiddled with by grandpascorpion on 20091006 at 01:47 
20091006, 13:57  #2  
Feb 2005
2^{2}×3^{2}×7 Posts 
Quote:
Suppose that phi(x)=n has m solution. Let p be large enough prime such that both q=2p+1 and r=2pn+1 are prime, but 2pd+1 is not prime for any dn and 1<d<n. Then phi(y)=2pn has m+1 solutions: m solutions of the form y=qx and one y=r. Here x goes over the solutions to phi(x)=n, while the choice of large p ensures that q and x are coprime. Last fiddled with by maxal on 20091006 at 14:02 

20091006, 14:43  #3 
Jan 2005
Transdniestr
503 Posts 
If r is prime though, both r and 2r will have the same phi. So, you would add two solutions there.

20091006, 14:57  #4 
Feb 2005
2^{2}·3^{2}·7 Posts 
Agree. The proof needs to be shaped out. But the general idea of getting m+k solutions out m solutions should work I believe.
btw, one needs to take into account odd x when 2qx also forms a solution. Last fiddled with by maxal on 20091006 at 15:03 
20091006, 15:24  #5 
Feb 2005
11111100_{2} Posts 
Actually, odd x brings no troubles, since in this case x'=2x is also one of m solutions (hence, 2qx=qx').
So, from m solutions one can get m+2 solutions  in particular, from 2 solutions one can get 4,6,8,... solutions; and from 3 solutions one can get 5,7,9,... solutions. Last fiddled with by maxal on 20091006 at 15:25 
20091007, 01:38  #7 
Jan 2005
Transdniestr
503 Posts 
Thanks, CR
