Results 1 to 8 of 8

Math Help - Eulers Totient

  1. #1
    Junior Member
    Joined
    May 2010
    Posts
    26

    Eulers Totient

    Hi Guys,

    Any information would be great.

    φ (30)
    Follow Math Help Forum on Facebook and Google+

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

    Re: Eulers Totient

    Quote Originally Posted by extatic View Post
    Hi Guys,

    Any information would be great.

    φ (30)
    The general expression of Euler's totiens function is...

    \varphi(n)= n\ \prod_{p|n} (1-\frac{1}{p}) (1)

    ... where p|n means 'prime deviding n'...

    Kind regards

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

  3. #3
    Junior Member
    Joined
    May 2010
    Posts
    26

    Re: Eulers Totient

    Thank you mate,

    Looking at this example, can you tell me how they came to use 2 & 3

    \varphi(36)=\varphi\left(2^2 3^2\right)=36\left(1-\frac{1}{2}\right)\left(1-\frac{1}{3}\right)=36\cdot\frac{1}{2}\cdot\frac{2}  {3}=12.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Junior Member
    Joined
    May 2010
    Posts
    26

    Re: Eulers Totient

    Quote Originally Posted by chisigma View Post
    The general expression of Euler's totiens function is...

    \varphi(n)= n\ \prod_{p|n} (1-\frac{1}{p}) (1)

    ... where p|n means 'prime deviding n'...

    Kind regards

    \chi \sigma
    Can you check if im correct please,

    Since 30 is not prime, we list all of the positive integers less than 30 that are relatively
    prime to it:

    1, 4, 7, 8, 9, 11 12, 13, 14, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29.

    \varphi(n)= (30) = 23
    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: Eulers Totient

    Quote Originally Posted by extatic View Post
    Can you check if im correct please,

    Since 30 is not prime, we list all of the positive integers less than 30 that are relatively
    prime to it:

    1, 4, 7, 8, 9, 11 12, 13, 14, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29.

    \varphi(n)= (30) = 23
    Because 30= 2 x 3 x 5, it is more easy to count the number 1 and all primes greater than 5 and less than 30: 1 , 7 , 11 , 13 , 17 , 19 , 23 , 29... total 8 numbers!...

    Kind regards

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

  6. #6
    Junior Member
    Joined
    May 2010
    Posts
    26

    Re: Eulers Totient

    So i attempted \varphi(n)= (10)

    10 = (2 * 5) = 10 * (1 - 1/2)(1 - 1/5)

    = 10 * (1/2 * 4/5)

    = 4/10 * 10/1

    = 4

    So there should be 4 prime numbers less than 10 (not including 2 and 5)

    1, 3, 7 (only three)

    What am i doing wrong?
    Follow Math Help Forum on Facebook and Google+

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

    Re: Eulers Totient

    Quote Originally Posted by extatic View Post
    So i attempted \varphi(n)= (10)

    10 = (2 * 5) = 10 * (1 - 1/2)(1 - 1/5)

    = 10 * (1/2 * 4/5)

    = 4/10 * 10/1

    = 4

    So there should be 4 prime numbers less than 10 (not including 2 and 5)

    1, 3, 7 (only three)

    What am i doing wrong?
    In my previous post I have been a little 'approximative'... if n is not prime, i.e. is...

    n= p_{1}^{k_{1}}\ p_{2}^{k_{2}}\ ...\ p_{i}^{k_{i}} (1)

    ... then the totiens function is 1 plus the number of primes p and their powers less than n. In Your case You have 'forgotten' 3 x 3=9...

    Kind regards

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

  8. #8
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,311
    Thanks
    691

    Re: Eulers Totient

    by the chinese remainder theorem, if p,q are distinct primes, \phi(p^rq^s) = \phi(p^r)\phi(q^s)

    thus it suffices to find \phi(p^r), where r is the highest power of p that divides n, for each prime p in the factorization of n.

    by counting (never underestimate the power of counting), \phi(p^r) = (p-1)(p^{r-1})

    so for n = 10, for example, 10 = (2)(5).

    φ(2) = 1, φ(5) = 4, so φ(10) = φ(2)φ(5) = (1)(4) = 4.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. totient function
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: October 2nd 2011, 09:10 AM
  2. Euler Totient
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: October 11th 2009, 04:38 PM
  3. Euler Totient
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: January 29th 2009, 09:46 PM
  4. Eulers totient function
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: January 22nd 2009, 02:21 AM
  5. Eulers totient function
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: January 14th 2009, 07:10 PM

Search Tags


/mathhelpforum @mathhelpforum