8
$\begingroup$

Let $\phi(n)$ be Euler's totient function.

How do I show that there are only finitely many such $n$ with $\phi(n) = m$, for each positive integer $m$?

I've written $n$ as a product of primes; $n = p_1^{c_1} \cdots p_k^{c_k}$, and then $\phi(n) = p_1^{c_1 - 1}(p_1 -1) \cdots p_k^{c_k - 1}(p_k - 1)$, I feel like this should help me but I can't seem to see why!

Also, out of interest, is it possible to represent every single integer $m$ in terms of the Euler totient function $\phi(n)$?

$\endgroup$
  • $\begingroup$ Step I: get an upper bound on the size of any prime $p$ dividing $n$. Step II: if $p\,|\,n$ for some prime $p$ get a bound on the exponent $a$ such that $p^a\,|\,n$. $\endgroup$ – lulu May 21 '18 at 9:43
  • $\begingroup$ For your second question: note that $\varphi(n) $ is almost always even. $\endgroup$ – lulu May 21 '18 at 9:44
5
$\begingroup$

First, note that for any $r$ there at most two numbers $s$ satisfying

  • $s$ is a prime power and
  • $\phi(s)=r$.

This is because the only possible options are $r+1$ or $\frac{pr}{p-1}$ where $p$ is the largest prime dividing $r$.

Second, we can write $n=s_1s_2\cdots s_k$ where each $s_i$ is a power of a different prime. Then if $\phi(s_i)=r_i$ for each $i$, we have $\phi(n)=r_1r_2\cdots r_k$ and we have at most one $i$ with $r_i=1$ (since this only occurs if $s_i=2$). There are only finitely many ways to write $m$ as a product of some positive integers $r_i$ with at most one $r_i=1$, and for each such product there are finitely many ways to reconstruct the $s_i$.

For the second question, numbers which don't appear as the totient function of other numbers are called "nontotients" - see the wikipedia article on them for more details.

$\endgroup$
  • $\begingroup$ Why are them two options the only two possibilities? $\endgroup$ – the man May 21 '18 at 11:40
  • $\begingroup$ @theman because if $s$ is prime then $\phi(s)=s-1$, whereas if $s=p^a$ is not prime ($a>1$) then $\phi(s)=p^{a-1}(p-1)$, and the largest prime factor of that is $p$. $\endgroup$ – Especially Lime May 21 '18 at 11:42
3
$\begingroup$

If $p^r\mid\mid n$, then $p^{r-1}(p-1))\mid\phi(n)$, which implies $\phi(n)\ge\max(p-1,p^{r-1})\ge\max(p-1,2^{r-1})$. Now if $m=\phi(n_1)=\phi(n_2)=\phi(n_3)=\cdots$ with $n_1\lt n_2\lt n_3\lt\cdots$, then for any prime power $p^r$ dividing any of the $n_k$'s we must have $p\le m+1$ and $r\le1+\log_2 m$. This put a finite upper bound on the sequence: If $n\gt((m+1)!)^{1+\log_2m}$, then $\phi(n)\gt m$.

Remark: The result here is nowhere near as good as the result $n\gt2m^2\implies\phi(n)\gt m$ in lhf's answer, but the proof here is nowhere near as complicated as the proof(s) linked to there.

$\endgroup$
  • $\begingroup$ Ah, I see this is essentially the same proof as in Especially Lime's answer. $\endgroup$ – Barry Cipra May 21 '18 at 21:39
2
$\begingroup$

It is known that $\phi(n) \geq \frac{\sqrt{n}}{\sqrt{2}}$. Therefore, if $\phi(n) = m$, then $n \le 2m^2$.

$\endgroup$
1
$\begingroup$

If there is a solution to $\phi(n) = m$ for a given $n$, what are the minimum and maximum possible values of $n$?

Assume that $m + 1$ is prime. Then $n = m + 1$ gives us the minimum possible solution. Of course if $m + 1$ is composite then the minimum $n$ will be correspondingly larger.

As for the maximum possible value of $n$, I figured it out a couple of years ago and then saw it confirmed in a book published before I was born, which is to say, very, very long ago.

Unfortunately I don't remember what it was. It was something like $m^2 - m$ for $m > 2$. No, that's overshooting it... The point is that if solutions exist, there is a minimum $n$ and a maximum $n$, and therefore the set of solutions is finite.

As for your last question, how would you handle numbers like $14$ and $26$?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.