Proof Two Primitive Root Conditions Are Equivalent

[golmschenk]

Homework Statement

Let n be a nonzero integer and let a be an integer with gcd(a, n) = 1. We have two equivalent conditions which characterize primitive roots:
(i) a is primitive modulo n if the order of a is $$\phi$$(n).
(ii) a is primitive modulo n if for every element b with gcd(b, n) = 1 we have b $$\equiv$$ a$$^{j}$$ mod n for some nonnegative integer j.
Write out the complete proof that condition (i) implies condition (ii). To do this, show first that the integers a$$^{0}$$, a$$^{1}$$,..., a$$^{\phi(n)-1}$$ must lie in distinct congruence classes modulo n. Then explain why this implies condition (ii).

2. The attempt at a solution
I'm trying to figure out how to do the first part of showing that a$$^{0}$$, a$$^{1}$$,..., a$$^{\phi(n)-1}$$ must lie in distinct congruence classes modulo n. I realize that because the numbers are relatively prime has to do something with it. How is the a number taken to a power related to a number it's relatively prime to? I don't necessarily even want the full answer for the question, just more a push in the right direction. I guess of course the full answer wouldn't be bad either though. Maybe with spoiler tags around it would be good? Thanks!

 

[Eynstone]

Let n be a nonzero integer and let a be an integer with gcd(a, n) = 1. We have two equivalent conditions which characterize primitive roots:
(i) a is primitive modulo n if the order of a is $$\phi$$(n).
(ii) a is primitive modulo n if for every element b with gcd(b, n) = 1 we have b $$\equiv$$ a$$^{j}$$ mod n for some nonnegative integer j.

If the order of a is k=$$\phi$$(n), {a$$^{i}$$ | i=1,2,..,k} is a reduced residue system mod n. If gcd(b, n) = 1 , b is congruent to some element in the
reduced residue system mod n & hence to a power of a.

 

[golmschenk]

If the order of a is k=$$\phi$$(n), {a$$^{i}$$ | i=1,2,..,k} is a reduced residue system mod n.

Why? Thanks!