Let $\phi$ denote Euler's $\phi$. If $\phi(n)=\phi(2n)$ then prove that $n$ is odd.
Solution
Suppose, on the contrary, that $n$ is even. We now recall that $\phi$ is defined as:
$$\phi(n)=n \prod_{d \mid n} \left( 1- \frac{1}{d} \right)$$
Now since $\phi$ is multiplicative then:
\begin{align*}
\phi(2m)=\phi(4m)&\Rightarrow \phi(2)\phi(m)=\phi(4)\phi(m)\\
&\Rightarrow \phi(2)=\phi(4)
\end{align*}
However, this is a contradiction since $\phi(2)=2 \cdot \frac{1}{2} =1$ and $\phi(4)=2$. The result follows.
Solution
Suppose, on the contrary, that $n$ is even. We now recall that $\phi$ is defined as:
$$\phi(n)=n \prod_{d \mid n} \left( 1- \frac{1}{d} \right)$$
Now since $\phi$ is multiplicative then:
\begin{align*}
\phi(2m)=\phi(4m)&\Rightarrow \phi(2)\phi(m)=\phi(4)\phi(m)\\
&\Rightarrow \phi(2)=\phi(4)
\end{align*}
However, this is a contradiction since $\phi(2)=2 \cdot \frac{1}{2} =1$ and $\phi(4)=2$. The result follows.
Your proof is not complete.
ReplyDeleteYou suppose that if $n$ is even then there exist $m$ such that $n=2m$ but $m$ dont need to be coprime with $n$ and so you cannot use multiplicative property of $\phi$.
If $n$ is even then there exist $m,r$ positive integers with $m$ odd, such that: $n=2^r\times m$
Thanks for raising a point there. Maybe (?) this direct proof.
ReplyDeleteIf $\gcd(2,n)=1$ (that is $n$ is odd) then:
$$\phi(2n)=\phi(2)\phi(n)=\phi(n)$$
holds.
Now, suppose that $n$ is even, that is $n=2^r m$ and $\gcd(2,m)=1$. Then:
$$\phi(n)=\phi\left(2^r \right) \phi(m)=2^r \left (1 - \frac{1}{2} \right) \phi(m)=2^{r-1} \phi(m)$$
while
$$\phi(2n)=\phi \left (2^{r+1} m \right)= \phi \left(2^{r+1} \right) \phi(m)=2^r \phi(m)$$
Thus $\phi(n) \neq \phi(2n)$ if $n$ is even. As a conclusion we have:
$$\phi(n)=\phi(2n) \Leftrightarrow n \; \text{is odd}$$
What do you think?
Speaking of Euler's totient function here is a similar property:
ReplyDelete$$2\phi(n)=\phi(2n) \Leftrightarrow n \; \text{is even}$$