Order of an element and GCD
I have the following problem which i can only solve half of it.
Problem: Let G = <g> be a cyclic group of order n. Prove that the order of is n/d, where d = gcd(n,k).
Solution: Since G has order n, order of g is n. i.e. =1. Also, d|k, giving da = k for some integer a. Hence, .
However, i am unable to show that n/d is the order. The only theorem about order that i know is that: If r is the order of g and , then r|k. is there any other theorems that i need to know to solve this problems. Thank You!.
Re: Order of an element and GCD
the trick is to first prove .
now k = db, so therefore:
writing d = ns + kt (which we can by the euclidean algorithm), we have:
so we also know that
so . this means that .
now obviously . suppose that
for some 0 < u < n/d. then 0 < du < n, but
contradicting the fact that the order of g is n. thus there can be no such u,