Find all $n \in \mathbb{Z^+} : \phi(n)=2$

Question

If $\phi$ is Euler's Phi Fuction we want to find all $n \in \mathbb{Z^+}: \phi(n)=2$.

First of all $n>2$. Let $n=2^k3^lm $ with $k,l\in \mathbb{N},\ m\in \mathbb{Z^+}$ with $\text{gdc}(m,2)=\text{gdc}(m,3)=1.$ So $\phi(n)=2 \iff \phi(2^k3^lm)=2 \iff \phi(2^k )\phi(3^l) \phi(m)=2 $

1. If $k,l>0 \implies 2^{k-1}3^{l-1}\phi(m)=2\implies k=l=1 ,\ m=1\implies n=6.$
2. If $k=0,\ l>0 \implies2\cdot3^{l-1}\phi(m)=2\implies l=1,\ m=1\implies n=3.$
3. If $l=0,\ k>0 \implies 2^{k-1}\phi(m)=2 \implies 2^{k-2}\phi(m)=1\implies k=2,\ m=1 \implies n=4.$
4. But what happens if $k=l=0 \implies n=m: \text{gcd}(m,6)=1$ ?

Thank you.

Answer 1

If $1<n=\prod p_i^{k_i}$ is the factorization in primes of $n$ we have $\phi(n)=\prod p_i^{k_i-1}(p_i-1)$. So if $\phi(n)=2$ we must have $p_i-1\in \{1,2\}$ and so $p_i\in \{2,3\}$ for all $i$. So $\gcd(n,6)=1$ isn't possible.

Answer 2

Hint: If $n \geq 7$, there are at least two primes less than $n$ that do not divide $n$.

Answer 3

For every integer $n\geq3$, there are at least $2$ smaller integers coprime to $n$, namely:

• $1$
• $n-1$

Hence $n\geq3\implies\phi(n)\geq2$.

---

For every integer $n>6$, there is at least $1$ more smaller integer coprime to $n$, namely:

• A prime number $p$ such that $\frac12n<p<n$

Hence $n>6\implies\phi(n)>2$.

---

This leaves us with only $4$ cases to check:

• $n=3\implies\phi(n)=\color\red2$
• $n=4\implies\phi(n)=\color\red2$
• $n=5\implies\phi(n)=4$
• $n=6\implies\phi(n)=\color\red2$