mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2009-10-06, 01:45   #1
grandpascorpion
 
grandpascorpion's Avatar
 
Jan 2005
Transdniestr

503 Posts
Default 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
grandpascorpion is offline   Reply With Quote
Old 2009-10-06, 13:57   #2
maxal
 
maxal's Avatar
 
Feb 2005

22·32·7 Posts
Default

Quote:
Originally Posted by grandpascorpion View Post
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
maxal is offline   Reply With Quote
Old 2009-10-06, 14:43   #3
grandpascorpion
 
grandpascorpion's Avatar
 
Jan 2005
Transdniestr

503 Posts
Default

If r is prime though, both r and 2r will have the same phi. So, you would add two solutions there.
grandpascorpion is offline   Reply With Quote
Old 2009-10-06, 14:57   #4
maxal
 
maxal's Avatar
 
Feb 2005

22×32×7 Posts
Default

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
maxal is offline   Reply With Quote
Old 2009-10-06, 15:24   #5
maxal
 
maxal's Avatar
 
Feb 2005

22×32×7 Posts
Default

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
maxal is offline   Reply With Quote
Old 2009-10-06, 22:07   #6
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

135248 Posts
Default

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
CRGreathouse is online now   Reply With Quote
Old 2009-10-07, 01:38   #7
grandpascorpion
 
grandpascorpion's Avatar
 
Jan 2005
Transdniestr

503 Posts
Default

Thanks, CR
grandpascorpion is offline   Reply With Quote
Reply

Thread Tools


All times are UTC. The time now is 04:16.

Tue Mar 2 04:16:42 UTC 2021 up 89 days, 28 mins, 0 users, load averages: 2.19, 1.79, 1.62

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.