There's something I'm a bit confused about.

There's a theorem that states that if the order of a group is n, then every k > 1 that satisifes gcd(k,n) = 1 will be a generator of the group.

No, what that theorem says is that if g is a generator of that cyclic group of order n, then any other

generator is of the form , and the other direction is true, too.

Tonio
So if we take U(9) = {1,2,4,5,7,8}, and the order n = 6 and the generators in this case are supposed to be 5 and 7, since gcd(5,6) = gcd(7,6) = 1.

<5> = {5,7,8,4,2,1} is okay, but

<7> = {7,4,1}

and instead <2> = {2,4,8,7,5,1}, even though gcd(2,6) = 2.

What's the problem here?