2
$\begingroup$

I found this exercise in Beachy and Blair: Abstract algebra:

Find all natural numbers $n$ such that $\varphi(n)=2$, where $\varphi(n)$ means the totient function.

My try:

$\varphi(n)=2$ if $n=3,4,6$ and I think that no other numbers have this property. So assume $n>7$.

Case 1: $n$ is prime, since $\varphi(n)=n-1$ for primes, no numbers here will have the desired property

Case 2: $n$ is of the form $n=p^k$ for some prime $p$ and $k\in\mathbb{N}, k\ge 2$. By Eulers formula we get $$ \varphi(n)=p^k-p^{k-1} $$ which clearly is greater than $2$ since $n>7$.

Case 3: $n$ is the product of different primes and is squarefree (each prime comes up at most once in the prime factorisation of $n$). Assume $$ n=\prod_{i=1}^{m} p_i $$ by Eulers formula $$ \varphi(n)=n\prod_{p_i \ prime \ factor}\Big(1-\frac{1}{p_i}\Big) $$ which gives $$ \varphi(n)=p_1p_2\cdot\ldots\cdot p_m\Big(1-\frac{1}{p_1}\Big)\Big(1-\frac{1}{p_2}\Big)\cdot \ldots\cdot \Big(1-\frac{1}{p_m}\Big) $$ rearranging and multiplying out gives $$ (p_1-1)(p_2-1)\cdot\ldots\cdot (p_m-1) $$ which once again has to be greater than $2$ since $n>7$.

Case 4: $n$ is a product of different primes and not squarefree. This is similar to Case 3 but we get some more factors in the product so if there were no integers in Case 3 there cannot be here eighter.

Now my first question is: Is my reasonning correct? Ususally when I have to divide the solution up into so many cases I feel that I haven't grasped the problem properly, but I couldn't come up with anything better.

Any suggestions?

Thank you in advance

$\endgroup$
  • 2
    $\begingroup$ If prime $p$ divides $n,p-1$ must divide $\phi(n)$ right? $\endgroup$ – lab bhattacharjee Jan 15 '18 at 9:18
2
$\begingroup$

Let $n = \prod p_i^{k_i}$ be the prime factorization of $n$.

Then $\phi(n) = \prod p_i^{k_i - 1}(p_i-1)$.

So if $2 = 1^w*2^1 = \prod p_i^{k_i - 1}(p_i-1)$ then all the $(p_i -1) $ equal either $1$ or $2$ so all the $p_i$ equal either $2$ or $3$.

So either we have

$n = p^k$ and either $p=2$ or $3$;

So 1) $n = 2^k$ or 2)$n = 3^k$

Or we have

3) $n = 2^k3^m$

If 1) then $\phi(n) = 2^{k-1}(2-1) = 2$ so $k= 2$ and $n=4$.

If 2) then $\phi(n) = 3^{k-1}(3-1) = 2$ so $k = 1$ and $n =3$.

If 3) then $\phi(n) = 2^{k-1}(2-1)3^{m-1}(3-1)$ so $k =1$ and $m =1$ and $n=6$.

Those are the only three cases.

$\endgroup$
1
$\begingroup$

It's fairly trivial to prove that $\phi(n)$ is divisible by $2$ for any $n \ge 3$. So if $n$ has two coprime factors, both bigger than $3$ we have that $4 \mid \phi(n)$. Therefore the only remaining cases are $n=2p^k$ and $n=p^k$, where $p$ is an odd prime. You should be able to derive a constrain for $p$ and $k$ from here, by noting that $\phi(p^k) \ge \phi(p) = p-1$

$\endgroup$
1
$\begingroup$

For every prime $p\geq 4$ and ever natural number $k$ you have $p^k-p^{k-1}>2$. Since $φ(ab)=φ(a)φ(b)$ if $(a,b)=1$ this means that if you have a prime number $p\geq4$ which $p|n$ then $φ(n)>2$. Therefore only $2$ and $3$ can divide $n$. But $2^{k_1}-2^{k_1-1}=2^{k_1-1}$ and $3^{k_2}-3^{k_2-1}\geq2$ for $k_2\geq2$ therefore $k_2$ can be only $0,1$ and $k_1$ can be only $0$,$1$,$2$.

Now we check.

If $k_1=0$ then only $3|n$ so $n=3$.

If $k_1=1$ then $2$ doesn't contribute to the function so again $k_2=1$ and now $n=6$.

Finally, if $k_1=2$ then $φ(4)=2$ and this forces $k_2=0$.

So you were right, $n$ can only be $3,4,6$.

$\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.