Hi,

I need help with this proof:

Prove that there are no integers n for which phi(n) = n/4

Appreciate any assistance

Printable View

- Mar 29th 2009, 11:00 AMhtata123euler phi-function
Hi,

I need help with this proof:

Prove that there are no integers n for which phi(n) = n/4

Appreciate any assistance - Mar 29th 2009, 11:10 AMThePerfectHacker
- Mar 29th 2009, 11:13 AMhtata123
I did that but I'm still stuck. Any ideas on how I should proceed?

- Mar 29th 2009, 07:42 PMThePerfectHacker
Certainly $\displaystyle n$ is divisible by $\displaystyle 4$ so we can write $\displaystyle n=2^a\cdot m$ where $\displaystyle a\geq 2$ and $\displaystyle m$ is a positive odd integer. Now, $\displaystyle \phi(n) = \phi(2^a)\phi(m) = 2^{a-1}\phi(m)$ since $\displaystyle (2^a,m)=1$. While $\displaystyle n/4 = 2^{a-2}m$. Therefore, if $\displaystyle \phi(n) = n/4$ then $\displaystyle 2^{a-1}\phi(m) = 2^{a-2}m\implies 2\phi(m) = m$. This is impossible because LHS is even while RHS is odd.