Prove that if , then has a subgroup of order .
There must exist a such that . How do I know there exists such an element in ?
how about n-1 (mod n)?
(there's one other element that always works, to make up "the rest of the subgroup". i'll leave it to you to discover. oh, and you'll want to show that gcd(n-1,n) = 1, as well).
well, of course 1 has the property that 1^{2} = 1 (mod n) (for any n, in fact).
4 has order 2 mod 5:
4^{2} = 16 = 1 (mod 5), so 4 is a generator (of a group of order 2).
if p is a prime, then U(p) will be cyclic (this is an involved proof, so i won't write it here), of order p-1.
as long as p > 2, then p will be odd, so U(p) (being cyclic) will have ONLY ONE element of order 2.
for a general n, there may be several elements of order 2 in U(n) (you get at least one for each prime factor of n).
Thanks. I am having trouble understanding some of your points at the moment.
>> if p is a prime, then U(p) will be cyclic (this is an involved proof, so i won't write it here), of order p-1.
I found a theorem in my notes saying that if then is cyclic if and only if or , where is a prime other than and is a positive integer. The proof of this should cover the case when is prime.
I need to think more about the other two points. I will come back later.
>> as long as p > 2, then p will be odd, so U(p) (being cyclic) will have ONLY ONE element of order 2.
>> (you get at least one for each prime factor of n).