# Math Help - 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 $
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 $
\phi \left( n \right) = \tfrac{n}
{2} \Rightarrow n = 2^a ,a \in \mathbb{Z}^ +
$

I'll present 2 proofs

1)

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

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

Now since $\phi$ is multiplicative : $
\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 $b=1$ then $\phi(n)=\tfrac{n}{2}$ indeed holds, however if $b>1$ then $
\phi \left( b \right) < b
$
( Since b is not coprime to itself now ), thus if $b>1$ we have $
\phi \left( n \right) = 2^{a-1} \cdot \phi \left( b \right)<2^{a-1} \cdot b = \tfrac{n}{2}
$
thus $\phi(n)= \tfrac{n}{2}$ is impossible when $b>1$ and we are done.

2)

We have $
\phi \left( n \right) = n \cdot \prod\limits_{\left. p \right|n} {\left( {1 - \tfrac{1}
{p}} \right)}
$
so we have: $
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}

$
$
\Leftrightarrow 2 \cdot \prod\limits_{\left. p \right|n} {\left( {p - 1} \right)} = \prod\limits_{\left. p \right|n} p
$

This means that $
2\left| {\left( {\prod\limits_{\left. p \right|n} p } \right)} \right.
$
So 2 must be one of the primes there $
\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
$
$
\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 ( $
p - 1 < p
$
) if there's a prime $q>2$ such that $q|n$. This means that 2 is the only prime dividing $n$ and we are done.