Given a positive integer k, show there are at most a finite number of integers n for which Φ(n)=k

Printable View

- Apr 27th 2009, 11:50 PMF350A proof using the phi-function
Given a positive integer k, show there are at most a finite number of integers n for which Φ(n)=k

- Apr 28th 2009, 12:58 PMMedia_ManBounding the function
It is already known that the totient function is bounded as follows:

$\displaystyle \sqrt{n} < \phi(n) < n-\sqrt{n}$

So, given an arbitrary positive integer $\displaystyle k$, $\displaystyle \phi(n)>k$ for all $\displaystyle n>k^2$. So the highest number $\displaystyle n$ satisfying $\displaystyle \phi(n)=k$ must still be less than $\displaystyle k^2$. Since there is such an upper bound, the total number of integers n satisfying this equality is finite.