Find Number of Generators in Z_(p^r)

[Eivind]

Let p be a prime number. Find the number of generators of the cyclic group Z_(p^r), where r is an integer >=1.

A small hint, please?

 

[Hurkyl]

What do you know about generators of cyclic groups?

 

[Eivind]

Well, the generators are those which are relatively prime to p^r.

 

[Hurkyl]

Well, the generators are those which are relatively prime to p^r.

And don't you know an algorithm for computing how many integers in the range [0, n] are relatively prime to any number n?