Results 1 to 2 of 2

Thread: Euler Phi-Function

  1. #1
    Newbie
    Joined
    May 2009
    Posts
    2

    Euler Phi-Function

    Can someone please help me with this proof.
    Find all n such that phi(n) = n/3.
    Any help is much appreciated.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member PaulRS's Avatar
    Joined
    Oct 2007
    Posts
    571
    To start with, note that, since $\displaystyle \phi(n)$ is either 1 or an even number, n must be even.

    Remember that: $\displaystyle
    \phi \left( n \right) = n \cdot \prod\limits_{\left. p \right|n} {\left( {1 - \tfrac{1}
    {p}} \right)}
    $ (the products go over the prime numbers p dividing n)

    Thus: $\displaystyle
    \phi \left( n \right) = \tfrac{n}
    {3} \Leftrightarrow \prod\limits_{\left. p \right|n} {\left( {1 - \tfrac{1}
    {p}} \right)} = \tfrac{1}
    {3} \Leftrightarrow 3 \cdot \prod\limits_{\left. p \right|n} {\left( {p - 1} \right)} = \prod\limits_{\left. p \right|n} p
    $

    Now since 3 is a prime number, and $\displaystyle
    3\left| {\prod\limits_{\left. p \right|n} p } \right.
    $ it follows that 3 is one of the prime factors in the product. Thus: $\displaystyle 2\cdot
    \prod\limits_{\left. p \right|n;p \ne 3} {\left( {p - 1} \right)} = \prod\limits_{\left. p \right|n;p \ne 3} p
    $ and 2|n thus: $\displaystyle
    \prod\limits_{\left. p \right|n;p \ne 3;p \ne 2} {\left( {p - 1} \right)} = \prod\limits_{\left. p \right|n;p \ne 3;p \ne 2} p
    $ and this is only possible if there are no other prime factors.

    Thus: $\displaystyle
    n = 2^\alpha \cdot 3^\beta
    $ with $\displaystyle \alpha,\beta\in \mathbb{Z}^+$

    And conversely this number satisfies the condition for any $\displaystyle \alpha,\beta\in \mathbb{Z}^+$
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Euler function
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: Nov 30th 2011, 09:53 AM
  2. Euler Function phi(n)
    Posted in the Number Theory Forum
    Replies: 22
    Last Post: May 29th 2010, 07:29 AM
  3. Euler's phi function
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: Apr 8th 2010, 02:58 PM
  4. Euler's phi function
    Posted in the Advanced Math Topics Forum
    Replies: 12
    Last Post: Jan 12th 2010, 05:10 AM
  5. Euler phi-Function
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: Mar 11th 2009, 06:11 PM

Search Tags


/mathhelpforum @mathhelpforum