1
$\begingroup$

Can anyone help me with this!? If $n=p_1^{k_1},p_2^{k_2},\ldots $ Then I applied the given condition of divisibility of $\varphi(n)$ but can't reach to a conclusion.

$\endgroup$
1
$\begingroup$

Hint: If $p^2 \mid n$, then $p \mid \phi(n)$.

Indeed, if $p^e$ is the power of $p$ appearing in the factorization of $n$, then $\phi(n)=\phi(p^e)\cdots=p^{e-1}(p-1)\cdots$.

$\endgroup$
  • $\begingroup$ Can you explain how? $\endgroup$ – Planck Feb 4 at 9:55
1
$\begingroup$

First, note that $\phi$ multiplicative. Then if $n=p_1^{k_1}\cdots p_m^{k_m}$, then $\phi(n)=\phi(p_1^{k_1})\cdots\phi(p_m^{k_m})$.

I believe you can prove that if for some prime $p$ and some $k\in\mathbb{Z^+}$, and $k>1$, then $p|\phi(p^k)$.

So suppose that some $k_i$ is greater than $1$. Then $p_i|\phi(p_i^{k_i})\hspace{0.2cm}|\phi(n)\hspace{0.2cm}|n-1$. But also, $p|n$. So, prime $p$ should be equal to $1$. Absurd....

$\endgroup$
1
$\begingroup$

If $p^2 \mid n$, then $p \mid \varphi(n)$, but obviously $p \nmid n-1$ and so $\varphi(n) \nmid n-1$.

$\endgroup$
1
$\begingroup$

we know that $n-\varphi(n)=\Pi\, p_i^{k_i-1}(\Pi\,p_i-\Pi\,(p_i-1))$ so if there is $k_i>1$ on the one hand we have $p_i|n-\varphi(n)$ and in the second one we know that $p_i|n$ then, $p_i|\varphi(n)$. So $p_i|n-1$ and $p_i|n$ ---> absurd so $k_i=1~~\forall i$

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