Results 1 to 3 of 3

Math Help - Euler Phi Func.

  1. #1
    Newbie
    Joined
    Feb 2007
    Posts
    23

    Euler Phi Func.

    Let n be a pos. int. The Euler Phi-func phi(n) is defined to be the # of pos. integers not exceeding n that are relatively prime to n.

    1a) Let n = 250. Find phi(n).

    b.) Determine the number of primitive roots n has.

    c.) Find any of these 5 primitive roots.

    Okay, so my book doesn't really go over how to find phi(n), except it gives a table of phi(n) up to n = 100. And then isn't primitive root just phi(phi(n)).

    I *believe* a.) is 100, although not sure how to show it, and then therefore b.) will be 40, although showing it is the issue. Probably the hardest part is c.)
    Last edited by flash101; April 19th 2007 at 10:53 PM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by flash101 View Post
    Let n be a pos. int. The Euler Phi-func phi(n) is defined to be the # of pos. integers not exceeding n that are relatively prime to n.

    1a) Let n = 250. Find phi(n).

    b.) Determine the number of primitive roots n has.

    c.) Find any of these 5 primitive roots.

    Okay, so my book doesn't really go over how to find phi(n), except it gives a table of phi(n) up to n = 100.
    Equation (8) here gives how to calculate it.



    And then isn't primitive root just phi(phi(n)).
    The number of primitive roots modulo n is phi(phi(n)).

    I *believe* a.) is 100, although not sure how to show it, and then therefore b.) will be 40, although showing it is the issue. Probably the hardest part is c.)
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Feb 2007
    Posts
    23
    Quote Originally Posted by CaptainBlack View Post
    Equation (8) here gives how to calculate it.





    The number of primitive roots modulo n is phi(phi(n)).
    Ah that helped a lot CaptainBlack.

    So I have phi(250) = phi(2^1*5^3) = 250(1 - 1/2)*(1 - 1/5) = 100

    So then part b is phi(100) = phi(2^2*5^2) = 100(1 - 1/2)*(1 - 1/5) = 40.. so yay I was right on my guess

    Now I'm stuck on part c!

    I tried following the method for doing c from http://faculty.uccb.ns.ca/jpreen/ntuccb05.pdf but it was very confusing.
    Last edited by flash101; April 19th 2007 at 10:53 PM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Euler path and Euler circuit problem
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: May 19th 2010, 08:18 PM
  2. Replies: 0
    Last Post: February 20th 2010, 08:26 AM
  3. Replies: 0
    Last Post: September 17th 2009, 06:44 PM
  4. euler func
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: December 9th 2007, 07:43 AM
  5. euler func.
    Posted in the Advanced Algebra Forum
    Replies: 13
    Last Post: December 1st 2007, 03:34 PM

Search Tags


/mathhelpforum @mathhelpforum