2
$\begingroup$

Show that if $n$ is a positive integer with $r$ distinct odd prime factors, then $2^r \mid \varphi(n)$.

So I know that $$\varphi(n) = \varphi(p_1^{a_1}\cdot p_2^{a_2} \cdots p_r^{a_r}) = (p_1^{a_1}-p_1^{a_1-1})(p_2^{a_2}-p_2^{a_2-1})\cdots(p_r^{a_r}-p_r^{a_r-1})=p_1^{a_1}(1-\frac{1}{p_1})p_2^{a_2}(1-\frac{1}{p_2}) \cdots p_r^{a_r}(1-\frac{1}{p_r}) = n\cdot (1-\frac{1}{p_1})(1-\frac{1}{p_2})(1-\frac{1}{p_r}).$$

and then I'm stuck. Any help would be appreciated!

$\endgroup$
  • 1
    $\begingroup$ Do you know the explicit formula for $\phi(n)$? This would follow from there. $\endgroup$ – астон вілла олоф мэллбэрг Mar 23 '17 at 1:33
  • $\begingroup$ If $p$ is one of the odd prime factors, what is $\phi(p)?$ $\endgroup$ – Will Jagy Mar 23 '17 at 1:34
3
$\begingroup$

Let $n=p_1\cdots p_r$ then $\varphi(p_i) = p_i-1 = 2k_i$ thus $\varphi(n)=2k_1\cdots 2k_r = 2^r\cdot(k_1\cdots k_r)$

So $\frac{2^r\cdot(k_1\cdots k_r)}{2^r} = (k_1\cdots k_r) \Rightarrow 2^r \mid \varphi(n)$

$\endgroup$
  • $\begingroup$ It's not clear to me that the OP means for $n$ to be square free. $\endgroup$ – B. Goddard Mar 23 '17 at 16:23
1
$\begingroup$

Note that in your formula, each $p^a-p^{a-1}$ is the difference of two odd integers, and hence is even. So you get a factor of 2 for each odd prime power that divides $n$.

$\endgroup$
0
$\begingroup$

$\varphi(ab)=\varphi(a)\varphi(b)$ when $gcd(a,b)=1$. $\varphi(p^k)=(p-1)[\text{stuff}]$, which is divisible by $2$. Combining these two facts gives the result, as each distinct prime factor introduces at least one multiple of $2$.

$\endgroup$
0
$\begingroup$

A counting argument. Definitely overkill.

In $R=\mathbb Z/n\mathbb Z$, Say that $x\sim y$ if $x^2=y^2$. Show $\sim$ is an equivalence relation.

Now if $x$ is a unit of $R$ and $x\sim y$ then show $y$ is a unit of $R$.

Finally, when $n$ is odd and $x$ is a unit, show that the $\sim$-equivalence class of $x$ has $2^r$ elements. (This is an application of the Chinese remainder theorem.)

So $\sim$ is an equivalence relation on the $\phi(n)$ units of $R$, and the equivalence classes all have size $2^r$.

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