6
$\begingroup$

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.

$\endgroup$
5
$\begingroup$

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}$$

$\endgroup$
  • 1
    $\begingroup$ I know it ,I can't use it and find all answer $\endgroup$ – amir bahadory Dec 30 '15 at 11:28
  • 1
    $\begingroup$ @amirbahadory I have added 1 point. Can you use it now? $\endgroup$ – SchrodingersCat Dec 30 '15 at 11:32
  • 2
    $\begingroup$ @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. $\endgroup$ – Hagen von Eitzen Dec 30 '15 at 11:46
  • $\begingroup$ @SchrodingersCat, Thanks $\endgroup$ – amir bahadory Dec 30 '15 at 11:59
  • $\begingroup$ @amirbahadory You're welcome. Have you got all the solutions? $\endgroup$ – SchrodingersCat Dec 30 '15 at 12:00
4
$\begingroup$

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$

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

$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^+$.

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