primitive roots: let r be prim rt of n; then r^k prim rt of

[patsobi]

let r be a primitive root of n. then r^k is a primitive root of n if and only if gcd(k,phi(n))=1. (phi(n) is Euler's function)

all I seem to be able to do here is write the information I know and I'm not able to get anything out of it, its driving me nuts, any help/hints would be great.

r^phi(n) = 1(mod n) and gcd(r,n)=1

=>
r^k is a primitive root of n
then:
r^[k*phi(n)] = 1(mod n) and gcd(r^k, n)=1
....

<=
gcd(k, phi(n))=1
....

 

[stapel]

let r be a primitive root of n. then r^k is a primitive root of n if and only if gcd(k,phi(n))=1.

Are you supposed to be proving this statement?

Thank you!

Eliz.