Find all positive integers n such that $\phi(n) |n$

I find $n=2^k ,2^k ×3^j$ is answer ,I can't find another answers.

HINT: Use the following fact-

For any positive integer $n$ with prime factorisation $$n=\prod_i^k p_i^{a_i}$$ where $p_i$'s are the prime factors of $n$, $$\phi(n)=n\prod_i^k\left(1-\frac{1}{p_i}\right)$$ $$=\prod_i^k p_i^{a_i-1}\left(p_i-1\right)$$

So, since you have $\phi(n)|n$, the required condition is $$\color{red}{\prod_i^k \left(p_i-1\right)|\prod_i^k p_i}$$

• I know it ,I can't use it and find all answer – amir bahadory Dec 30 '15 at 11:28
• @amirbahadory I have added 1 point. Can you use it now? – SchrodingersCat Dec 30 '15 at 11:32
• @amirbahadory Assume that some $p_i>3$ occurs. Then the factor $p_i-1$ on the left is either a power of $2$ and hence a multiple of $4$, or it is divisible by an odd prime $q<p_i$. In the latter case, $q$ is among the prime factors, hence the even number $q-1$ occurs on the left. Hence in both cases the left hand side is a multiple of $4$, but the right hand side is not. – Hagen von Eitzen Dec 30 '15 at 11:46
• @SchrodingersCat, Thanks – amir bahadory Dec 30 '15 at 11:59
• @amirbahadory You're welcome. Have you got all the solutions? – SchrodingersCat Dec 30 '15 at 12:00

Using the formula for $\phi (n)$ as pointed out be @ScrondingersCat,

the $\phi (n) |n$ is equivalent to

$s=(p_1-1)(p_2-1)....(p_k-1)|p_1p_2p_3.....p_k=t$

Assume WLOG $p_1=2$ (else $t$ is odd which is not possible except when $n=1$

Since, we must have $v_2(s) \leq v_2(t)=1$.

So, $v_2(s)=1$ which gives $k=2$ or $v_2(s)=0$ which gives $n=2^m$

Now,for $k=2$ we have $p_2-1|2p_2$. So, $p_2=3$

So, $n=2^m3^j$

• What is $v(a)$ ? – amir bahadory Dec 30 '15 at 11:43
• @amirbahadory, $v_2(a)$ means highest power of 2 in a (highest power of 2 that divides. It is the standard notation. – Subham Jaiswal Dec 30 '15 at 11:44
• Please don't use the same symbol, $k$, for the number of prime factors of $n$ and for $v_2(n)$. – A.P. Dec 30 '15 at 11:51
• @A.P. , Thanks for pointing out. – Subham Jaiswal Dec 30 '15 at 12:12

$n=1$ is a solution. If $n\ge 2$, then let $n=p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_k^{\alpha_k}$ be the unique prime factorization of $n$ with $p_1<p_2<\cdots < p_k$ and $\alpha_1,\alpha_2,\ldots,\alpha_k\ge 1$.

$$\phi(n)=p_1^{\alpha_1-1}p_2^{\alpha_2-1}\cdots p_k^{\alpha_k-1}(p_1-1)(p_2-1)\cdots (p_k-1)$$

$$\phi(n)\mid n\iff \frac{p_1p_2\cdots p_k}{(p_1-1)(p_2-1)\cdots (p_k-1)}\in\mathbb Z$$

If $k=1$, then $p_1-1\mid p_1$, so $p_1-1\mid p_1-(p_1-1)=1$, so $p_1=2$ and $n=2^{\alpha_1}$, which is a solution for all $\alpha_1\in\mathbb Z^+$.

If $k\ge 3$, then the denominator is divisible by $4$ but the numerator is not.

If $k=2$, then $(p_1-1)(p_2-1)\mid p_1p_2$. Also $\gcd(p_2-1,p_2)=1$ and $p_2-1>1$, so $p_2-1=p_1$, so $p_2=3$, $p_1=2$, so $n=2^{\alpha_1} 3^{\alpha_2}$, which is a solution for all $\alpha_1,\alpha_2\in\mathbb Z^+$.