# Thread: Euler's Theorem and Function

1. ## Euler's Theorem and Function

show that phi(n)=n/2 iff n=2^k for some positive integer k.

2. Proving that $\displaystyle n = 2^a ,a \in \mathbb{Z}^ + \Rightarrow \phi \left( n \right) = \tfrac{n} {2}$ is a fairly easy so we will prove the converse $\displaystyle \phi \left( n \right) = \tfrac{n} {2} \Rightarrow n = 2^a ,a \in \mathbb{Z}^ +$

I'll present 2 proofs

1)

If $\displaystyle n$ is odd, then $\displaystyle \tfrac{n}{2}$ is not an integer, so $\displaystyle \phi(n)=\tfrac{n}{2}$ is impossible since the LHS is an integer. Thus for that equality to hold, $\displaystyle n$ has to be even.

Then write $\displaystyle n = 2^a \cdot b$ with $\displaystyle a\in \mathbb{Z}^+$ and $\displaystyle (b,2)=1$

Now since $\displaystyle \phi$ is multiplicative : $\displaystyle \phi \left( n \right) = \phi \left( {2^a \cdot b} \right) = \phi \left( {2^a } \right) \cdot \phi \left( b \right) = 2^{a-1} \cdot \phi \left( b \right)$

If $\displaystyle b=1$ then $\displaystyle \phi(n)=\tfrac{n}{2}$ indeed holds, however if $\displaystyle b>1$ then $\displaystyle \phi \left( b \right) < b$ ( Since b is not coprime to itself now ), thus if $\displaystyle b>1$ we have $\displaystyle \phi \left( n \right) = 2^{a-1} \cdot \phi \left( b \right)<2^{a-1} \cdot b = \tfrac{n}{2}$ thus $\displaystyle \phi(n)= \tfrac{n}{2}$ is impossible when $\displaystyle b>1$ and we are done.

2)

We have $\displaystyle \phi \left( n \right) = n \cdot \prod\limits_{\left. p \right|n} {\left( {1 - \tfrac{1} {p}} \right)}$ so we have: $\displaystyle n \cdot \prod\limits_{\left. p \right|n} {\left( {1 - \tfrac{1} {p}} \right)} = \tfrac{n} {2} \Leftrightarrow \prod\limits_{\left. p \right|n} {\left( {1 - \tfrac{1} {p}} \right)} = \tfrac{1} {2}$ $\displaystyle \Leftrightarrow 2 \cdot \prod\limits_{\left. p \right|n} {\left( {p - 1} \right)} = \prod\limits_{\left. p \right|n} p$

This means that $\displaystyle 2\left| {\left( {\prod\limits_{\left. p \right|n} p } \right)} \right.$ So 2 must be one of the primes there $\displaystyle \Rightarrow 2 \cdot \prod\limits_{\left. p \right|n;p > 2} {\left( {p - 1} \right)} = 2 \cdot \prod\limits_{\left. p \right|n;p > 2} p$ $\displaystyle \Rightarrow \prod\limits_{\left. p \right|n;p > 2} {\left( {p - 1} \right)} = \prod\limits_{\left. p \right|n;p > 2} p$ (now the product goes over the prime divisors of n which are greater than 2). But this obviously can't hold ( $\displaystyle p - 1 < p$) if there's a prime $\displaystyle q>2$ such that $\displaystyle q|n$. This means that 2 is the only prime dividing $\displaystyle n$ and we are done.