# Proof Two Primitive Root Conditions Are Equivalent

## 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!

Related Calculus and Beyond Homework Help News on Phys.org
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.

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