3
$\begingroup$

Let $\phi(n) $ be Euler's Totient Function

Let us consider $$ |\{ n \in \mathbb{N} : \phi (n) = 8 \} | = 5, $$ and $$ |\{ n \in \mathbb{N} : \phi (n) = 14 \} | = 0. $$

How would I go about proving this?

$\endgroup$
3
$\begingroup$

If there are $r\ge1$ odd primes that divide $n$, then $2^r$ divides $\phi(n)$ (*). And if $2^t$ ($t\ge1$) divides $n$ then $2^{t-1}$ divides $\phi(n)$.

Therefore, if $\phi(n)=14$, then $n$ is the power of an odd prime ($n=p^s$) or its double ($n=2p^s$). Any case, $\phi(n)=p^{s-1}(p-1)$ so we have two possibilities:

  • If $s>1$ then $p^{s-1}$ divides $14$, that is, $p=7$ and $s=2$, but $\phi(7^2)=42$.
  • If $s=1$ then $p=n$ and $\phi(n)=n-1$, but $15$ is not prime.

Thus, there is no $n$ such that $\phi(n)=14$.

Can you now try with $8$? It's not very different.

Proof of (*): Let $p_1,\ldots,p_r$ be the odd prime factors of $n$. Then $$n=2^k\prod_{j=1}^r p_j^{\alpha_j}$$ for some $k\ge 0$ and $$\phi(n)=\phi(2^k)\prod_{j=1}^r(p_j-1)p_j^{\alpha_j-1}$$

Sinnce every $p_j-1$ is even, $2^r$ divides $\phi(n)$.

$\endgroup$
  • $\begingroup$ "If there are $r\ge 1$ odd primes that divide n" is it the true for every n > 2? $\endgroup$ – user180834 Jan 30 '15 at 20:25

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.