Results 1 to 3 of 3

Math Help - Euler's phi function proof

  1. #1
    Super Member
    Joined
    Feb 2008
    Posts
    535

    Euler's phi function proof

    I will denote Eulers' phi function by the symbol &.
    For example, &(10) = 10(1-1/2)(1-1/5) = 4
    So, there are 4 integers which are less than or equal to 10 that are relativley prime to 10...

    Show that if n>2, then &(n) is even.

    Thanks in advance for any help...
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
    Quote Originally Posted by jzellt View Post
    I will denote Eulers' phi function by the symbol &.
    For example, &(10) = 10(1-1/2)(1-1/5) = 4
    So, there are 4 integers which are less than or equal to 10 that are relativley prime to 10...

    Show that if n>2, then &(n) is even.

    Thanks in advance for any help...
    Suppose  n=p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_k^{\alpha_k} .

    Then  \phi(n) = \prod_{i=1}^k p_i^{\alpha_i-1}(p_i-1) .

    Now we are guaranteed to have at least one  p_j>2 , which means  p_j-1 is even. So we're done.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor Amer's Avatar
    Joined
    May 2009
    From
    Jordan
    Posts
    1,093
    Quote Originally Posted by jzellt View Post
    I will denote Eulers' phi function by the symbol &.
    For example, &(10) = 10(1-1/2)(1-1/5) = 4
    So, there are 4 integers which are less than or equal to 10 that are relativley prime to 10...

    Show that if n>2, then &(n) is even.

    Thanks in advance for any help...
    suppose

    n = p_1^{r_1} \cdot p_2^{r_2} \cdot \cdot \cdot  p_t^{r_t}

    r_i are exponents (powers for the primes)

    \phi(n) =\phi(p_1^{r_1} \cdot p_2^{r_2} \cdot \cdot \cdot  p_t^{r_t})

    as you know
    if p >2
    \phi(p^s) = p^{s-1}(p-1) but p-1 is even since p is odd so phi(p^s) is even for all p>2

    so

    \phi(n) =\phi(p_1^{r_1} \cdot p_2^{r_2} \cdot \cdot \cdot  p_t^{r_t})=\phi(p_1^{r_1})\cdot \phi(p_2^{r_2})\cdot \cdot \cdot \phi(p_t^{r_t})

    it a multiple of even numbers so n is even
    if any of p_i's equal 2 then phi of this is even or power of 2
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] Euler function proof
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: July 23rd 2011, 08:44 AM
  2. Euler's totient function Proof
    Posted in the Number Theory Forum
    Replies: 5
    Last Post: March 10th 2011, 05:30 AM
  3. Euler Function Proof
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: February 5th 2011, 12:04 AM
  4. Proof about Euler's φ-function
    Posted in the Advanced Algebra Forum
    Replies: 5
    Last Post: September 28th 2010, 01:13 PM
  5. Euler phi function proof
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: November 29th 2009, 09:58 PM

Search Tags


/mathhelpforum @mathhelpforum