Phi Question

[grandpascorpion]

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.

[maxal]

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.

[grandpascorpion]

If r is prime though, both r and 2r will have the same phi. So, you would add two solutions there.

[maxal]

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.

[maxal]

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.

[CRGreathouse]

Sloane's A007374 is relevant here. Noe gives the first example through m = 778.

[grandpascorpion]

Thanks, CR