Results 1 to 2 of 2

Math Help - Euler's Theorem and Function

  1. #1
    Junior Member
    Joined
    May 2008
    Posts
    55

    Question Euler's Theorem and Function

    show that phi(n)=n/2 iff n=2^k for some positive integer k.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member PaulRS's Avatar
    Joined
    Oct 2007
    Posts
    571
    Proving that <br />
n = 2^a ,a \in \mathbb{Z}^ +   \Rightarrow \phi \left( n \right) = \tfrac{n}<br />
{2}<br />
is a fairly easy so we will prove the converse <br />
\phi \left( n \right) = \tfrac{n}<br />
{2} \Rightarrow n = 2^a ,a \in \mathbb{Z}^ +  <br />

    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 <br />
n = 2^a  \cdot b<br />
with a\in \mathbb{Z}^+ and (b,2)=1

    Now since \phi is multiplicative : <br />
\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)<br />

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

    2)

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

    This means that <br />
 2\left| {\left( {\prod\limits_{\left. p \right|n} p } \right)} \right.<br />
 So 2 must be one of the primes there <br />
 \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 <br />
<br />
 \Rightarrow \prod\limits_{\left. p \right|n;p > 2} {\left( {p - 1} \right)}  = \prod\limits_{\left. p \right|n;p > 2} p <br />
(now the product goes over the prime divisors of n which are greater than 2). But this obviously can't hold ( <br />
p - 1 < p<br />
) 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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 4
    Last Post: January 10th 2011, 09:51 AM
  2. Replies: 1
    Last Post: October 23rd 2010, 04:12 PM
  3. Euler's Phi Function and Chinese Remainder Theorem
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: June 2nd 2008, 05:52 PM
  4. euler function and theorem
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: November 30th 2007, 12:59 PM
  5. Euler's theorem
    Posted in the Advanced Algebra Forum
    Replies: 3
    Last Post: February 25th 2007, 01:53 PM

Search Tags


/mathhelpforum @mathhelpforum