Results 1 to 5 of 5

Math Help - Euler function proof

  1. #1
    Junior Member
    Joined
    Feb 2010
    Posts
    45

    Euler function proof

    Show that \phi(n) = 14 is impossible.

    My guess would be to start by assuming \phi(n) = 14 and try to find a contradiction.

    \phi(15) = 14 would be true if 15 is prime. But it is not. \phi(15) = \phi(3)\phi(5) = (2)(4) = 8.

    Not sure where to go after this. Any help is appreciated.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor alexmahone's Avatar
    Joined
    Oct 2008
    Posts
    1,074
    Thanks
    7

    Re: Euler function proof

    Quote Originally Posted by Zalren View Post
    Show that \phi(n) = 14 is impossible.

    My guess would be to start by assuming \phi(n) = 14 and try to find a contradiction.

    \phi(15) = 14 would be true if 15 is prime. But it is not. \phi(15) = \phi(3)\phi(5) = (2)(4) = 8.

    Not sure where to go after this. Any help is appreciated.
    Let n=\prod p_i^{\alpha}

    \phi(n)=n\prod(1-\frac{1}{p_i})

    \phi(n)=\frac{n}{\prod p_i}\prod (p_i-1)

    Clearly, the factor 7 in 14 cannot come from p_i-1 because 8 and 15 are not prime. Edit: On second thoughts, I guess there could be a p_i like 29, so this proof is no longer valid.

    So n must be divisible by 49 and p_i=7

    But then \phi(n) would be divisible by 7-1 = 6, which is a contradiction.
    Last edited by alexmahone; July 23rd 2011 at 09:25 AM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor chisigma's Avatar
    Joined
    Mar 2009
    From
    near Piacenza (Italy)
    Posts
    2,162
    Thanks
    5

    Re: Euler function proof

    Quote Originally Posted by Zalren View Post
    Show that \phi(n) = 14 is impossible.

    My guess would be to start by assuming \phi(n) = 14 and try to find a contradiction.

    \phi(15) = 14 would be true if 15 is prime. But it is not. \phi(15) = \phi(3)\phi(5) = (2)(4) = 8.

    Not sure where to go after this. Any help is appreciated.
    If n= p_{1}\ p_{2}\ ... p_{k} , each p_{i}, i=1,2,...,k prime, then is...

    \varphi(n)= (p_{1}-1)\ (p_{2}-1)\ ... (p_{k}-1) (1)

    But the only possible factorisation of \varphi(n) is \varphi(n)=14 = 2*7 and it exists a prime p_{1} for which is p_{1}-1=2 but no prime p_{2} for which is p_{2}-1=7...

    Kind regards

    \chi \sigma
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor alexmahone's Avatar
    Joined
    Oct 2008
    Posts
    1,074
    Thanks
    7

    Re: Euler function proof

    Quote Originally Posted by chisigma View Post
    If n= p_{1}\ p_{2}\ ... p_{k} , each p_{i}, i=1,2,...,k prime, then is...

    \varphi(n)= (p_{1}-1)\ (p_{2}-1)\ ... (p_{k}-1) (1)

    But the only possible factorisation of \varphi(n) is \varphi(n)=14 = 2*7 and it exists a prime p_{1} for which is p_{1}-1=2 but no prime p_{2} for which is p_{2}-1=7...

    Kind regards

    \chi \sigma
    What if n is of the form \prod p_i^{\alpha} where all the powers are not 1?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor chisigma's Avatar
    Joined
    Mar 2009
    From
    near Piacenza (Italy)
    Posts
    2,162
    Thanks
    5

    Re: Euler function proof

    Quote Originally Posted by alexmahone View Post
    What if n is of the form \prod p_i^{\alpha} where all the powers are not 1?
    In this case is...

     n= p_{1}^{\alpha_{1}}\ p_{2}^{\alpha_{2}}\ ...\ p_{k}^{\alpha_{k}} (1)

    ... and...

    \varphi(n) = p_{1}^{\alpha_{1}-1}\ (p_{1}-1)\ p_{2}^{\alpha_{2}-1}\ (p_{2}-1)\ ...\ p_{k}^{\alpha_{k}-1}\ (p_{k}-1) (2)

    Also in this case is \varphi(n)= 2*7 and it exists a couple of numbers p_{1},\alpha_{1} for which is p_{1}^{\alpha_{1}-1}\ (p_{1}-1)=2 but no couple of numbers p_{2},\alpha_{2} for which is p_{2}^{\alpha_{2}-1}\ (p_{2}-1)=7...

    Kind regards

    \chi \sigma
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Euler's totient function Proof
    Posted in the Number Theory Forum
    Replies: 5
    Last Post: March 10th 2011, 06:30 AM
  2. Euler Function Proof
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: February 5th 2011, 01:04 AM
  3. Proof about Euler's φ-function
    Posted in the Advanced Algebra Forum
    Replies: 5
    Last Post: September 28th 2010, 02:13 PM
  4. Euler's phi function proof
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: April 7th 2010, 09:46 PM
  5. Euler phi function proof
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: November 29th 2009, 10:58 PM

/mathhelpforum @mathhelpforum