Results 1 to 2 of 2

Thread: Euler's Theorem and Function

  1. #1
    Junior Member
    May 2008

    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
    Oct 2007
    Proving that $\displaystyle
    n = 2^a ,a \in \mathbb{Z}^ + \Rightarrow \phi \left( n \right) = \tfrac{n}
    $ 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


    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.


    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}
    \Leftrightarrow \prod\limits_{\left. p \right|n} {\left( {1 - \tfrac{1}
    {p}} \right)} = \tfrac{1}

    $ $\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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 4
    Last Post: Jan 10th 2011, 08:51 AM
  2. Replies: 1
    Last Post: Oct 23rd 2010, 03:12 PM
  3. Euler's Phi Function and Chinese Remainder Theorem
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: Jun 2nd 2008, 04:52 PM
  4. euler function and theorem
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: Nov 30th 2007, 11:59 AM
  5. Euler's theorem
    Posted in the Advanced Algebra Forum
    Replies: 3
    Last Post: Feb 25th 2007, 12:53 PM

Search Tags

/mathhelpforum @mathhelpforum