Proving Finite Solutions of phi(x)=n for Fixed Integer n

[b0mb0nika]

for n- fixed integer prove that
phi(x)=n has a finite number of solutions
I looked at 2 cases when x is even and when x is odd
1) if x is even then phi(2x)>phi(x) and I showed why it has a finite number of solutions
2) I'm not sure how to show for the case when x is odd.. any ideas?

thanks :)

 

[shmoe]

You don't need to split into even/odd. Have you seen the inequality $$\phi(x)\geq \sqrt{x}$$? (valid if x is not 2 or 6). This isn't too difficult to show and gives a bound on the number of x's for a given n. Though if you have the even case already, you could prove the above inequality is always true for odd x.


You could also use the fact that phi is multiplicative. Show that there are a finite number of primes p that will satisfy $$\phi(p)\leq n$$. For each of these primes there is a finite number of exponents k that will satisfy $$\phi(p^k)\leq n$$. Conclude there are finitely many x with $$\phi(x)\leq n$$.

 

[b0mb0nika]

i think i got it.. i proved it using the fact that it's multiplicative thanks :rofl: