Results 1 to 2 of 2

Math Help - 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 \phi(n) is either 1 or an even number, n must be even.

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

    Thus: <br />
\phi \left( n \right) = \tfrac{n}<br />
{3} \Leftrightarrow \prod\limits_{\left. p \right|n} {\left( {1 - \tfrac{1}<br />
{p}} \right)}  = \tfrac{1}<br />
{3} \Leftrightarrow 3 \cdot \prod\limits_{\left. p \right|n} {\left( {p - 1} \right)}  = \prod\limits_{\left. p \right|n} p <br />

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

    Thus: <br />
n = 2^\alpha   \cdot 3^\beta  <br />
with \alpha,\beta\in \mathbb{Z}^+

    And conversely this number satisfies the condition for any \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: November 30th 2011, 10:53 AM
  2. Euler Function phi(n)
    Posted in the Number Theory Forum
    Replies: 22
    Last Post: May 29th 2010, 08:29 AM
  3. Euler's phi function
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: April 8th 2010, 03:58 PM
  4. Euler's phi function
    Posted in the Advanced Math Topics Forum
    Replies: 12
    Last Post: January 12th 2010, 06:10 AM
  5. Euler phi-Function
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: March 11th 2009, 07:11 PM

Search Tags


/mathhelpforum @mathhelpforum