# Math Help - Characterize integers, divisibility.

1. ## Characterize integers, divisibility.

ChallangeProblem.
Characterize all the the positive integers $n$ such that $\phi(n)|n$. ( $\phi$ is Euler's Phi-Function.)

Moderator edit: Approved challenge question.

2. Originally Posted by melese
ChallangeProblem.
Characterize all the the positive integers $n$ such that $\phi(n)|n$. ( $\phi$ is Euler's Phi-Function.)

Moderator edit: Approved challenge question.

Spoiler:
If $\displaystyle{n=p_1^{a_1}\cdot\ldots\cdot p_r^{a_r}}\,,\,\,p_i$ primes, $a_i\in\mathbb{N}$ , and since $\displaystyle{\phi(n)=n\prod\limits^r_{k=1}\left(1-\frac{1}{p_k}\right)}$ , we

get that $\displaystyle{\phi(n)\mid n\Longleftrightarrow 1=m\prod\limits^r_{k=1}\left(1-\frac{1}{p_k}\right)}\,,\,m\in\mathbb{N}$ , so the factors on the RHS are inverse

to each other, and this means $\displaystyle{\prod\limits^r_{k=1}\left(1-\frac{1}{p_k}\right)^{-1}=\prod\limits^r_{k=1}\frac{p_k}{p_k-1}\right)}\in\mathbb{N}$.

But the only prime that $p_k-1$ divides is $2$ , unless $p_k=2$ and $p_k-1=1$ , in which case

only the prime $p_j=3$ can possibly be so that $(p_j-1)=2\mid 2=p_k$ , so n has to be of the form

$n=2^r3^s\,,\,r>0\,,\,s\geq 0$ .

Tonio