- #1
- 3,149
- 8
Homework Statement
Let <a> be a cyclic group, where ord(a) = n. Then a^r generates <a> iff r and n are relatively prime.
The Attempt at a Solution
OK, let n and r be relatively prime. Then ord(a^r) = n. We need to show that for some j, there exists an integer k such that (a^r)^k = a^j. Now, every power of a equals one of the powers in <a>. Hence, for any k, a^(rk) equals some a^p. By inspecting the proof of that fact, I concluded that the power rk+1, equals a^(p+1), if we keep all the factors obtained by the division algorithm the same, and only increase the remainder by 1 (I don't see why we couldn't do this). This way, we can generate every element of <a>, and hence a^r generates <a>.
Now, for the other direction, if a^r generates <a>, and if we show that ord(a^r) = n, then we are done, since r and n must be relatively prime then (I proved this fact in another exercise). We see that (a^r)^n = (a^n)^r = e. Now, assume there is some j < n such that (a^r)^j = e. But the, since a^r is a generator of <a>, <a> would have less than n elements, contrary to the starting assumption, hence the order of a^r equals n.