- #1

- 36

- 0

## 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 [tex]\phi[/tex](n).

(ii) a is primitive modulo n if for every element b with gcd(b, n) = 1 we have b [tex]\equiv[/tex] a[tex]^{j}[/tex] 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[tex]^{0}[/tex], a[tex]^{1}[/tex],..., a[tex]^{\phi(n)-1}[/tex] 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[tex]^{0}[/tex], a[tex]^{1}[/tex],..., a[tex]^{\phi(n)-1}[/tex] 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!