Results 1 to 5 of 5

Thread: Euler function proof

  1. #1
    Junior Member
    Joined
    Feb 2010
    Posts
    45

    Euler function proof

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

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

    $\displaystyle \phi(15) = 14$ would be true if 15 is prime. But it is not. $\displaystyle \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,114
    Thanks
    7

    Re: Euler function proof

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

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

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

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

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

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

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

    So n must be divisible by 49 and $\displaystyle p_i=7$

    But then $\displaystyle \phi(n)$ would be divisible by 7-1 = 6, which is a contradiction.
    Last edited by alexmahone; Jul 23rd 2011 at 08: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
    6

    Re: Euler function proof

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

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

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

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

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

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

    Kind regards

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

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

    Re: Euler function proof

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

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

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

    Kind regards

    $\displaystyle \chi$ $\displaystyle \sigma$
    What if n is of the form $\displaystyle \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
    6

    Re: Euler function proof

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

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

    ... and...

    $\displaystyle \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 $\displaystyle \varphi(n)= 2*7$ and it exists a couple of numbers $\displaystyle p_{1},\alpha_{1}$ for which is $\displaystyle p_{1}^{\alpha_{1}-1}\ (p_{1}-1)=2$ but no couple of numbers $\displaystyle p_{2},\alpha_{2}$ for which is $\displaystyle p_{2}^{\alpha_{2}-1}\ (p_{2}-1)=7$...

    Kind regards

    $\displaystyle \chi$ $\displaystyle \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: Mar 10th 2011, 05:30 AM
  2. Euler Function Proof
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: Feb 5th 2011, 12:04 AM
  3. Proof about Euler's φ-function
    Posted in the Advanced Algebra Forum
    Replies: 5
    Last Post: Sep 28th 2010, 01:13 PM
  4. Euler's phi function proof
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: Apr 7th 2010, 08:46 PM
  5. Euler phi function proof
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: Nov 29th 2009, 09:58 PM

/mathhelpforum @mathhelpforum