Thread: 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.)

Originally Posted by flash101

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.)

Originally Posted by CaptainBlack

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.