# Euler Phi Func.

• Apr 18th 2007, 10:34 PM
flash101
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.)
• Apr 18th 2007, 11:15 PM
CaptainBlack
Quote:

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.

Quote:

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

Quote:

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.)
• Apr 19th 2007, 10:41 PM
flash101
Quote:

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.