mersenneforum.org > Math Phi Question
 Register FAQ Search Today's Posts Mark Forums Read

 2009-10-06, 01:45 #1 grandpascorpion     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 2009-10-06 at 01:47
2009-10-06, 13:57   #2
maxal

Feb 2005

22×32×7 Posts

Quote:
 Originally Posted by grandpascorpion 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.
This is true if we assume existence of certain prime constellations.

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 d|n 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 co-prime.

Last fiddled with by maxal on 2009-10-06 at 14:02

 2009-10-06, 14:43 #3 grandpascorpion     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.
 2009-10-06, 14:57 #4 maxal     Feb 2005 22·32·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 2009-10-06 at 15:03
 2009-10-06, 15:24 #5 maxal     Feb 2005 111111002 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 2009-10-06 at 15:25
 2009-10-06, 22:07 #6 CRGreathouse     Aug 2006 32·5·7·19 Posts Sloane's A007374 is relevant here. Noe gives the first example through m = 778. Last fiddled with by CRGreathouse on 2009-10-06 at 22:07
 2009-10-07, 01:38 #7 grandpascorpion     Jan 2005 Transdniestr 503 Posts Thanks, CR