# Order of an element and GCD

• Oct 9th 2011, 04:20 AM
H12504106
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 \$\displaystyle g^k\$ is n/d, where d = gcd(n,k).

Solution: Since G has order n, order of g is n. i.e. \$\displaystyle g^n\$=1. Also, d|k, giving da = k for some integer a. Hence, \$\displaystyle ({g^k})^{n/d} = g^{(nk)/d} = g^{(ndb)/d} = {(g^n)}^b = 1\$.

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 \$\displaystyle g^m =1\$, then r|k. is there any other theorems that i need to know to solve this problems. Thank You!.
• Oct 9th 2011, 05:33 AM
Deveno
Re: Order of an element and GCD
the trick is to first prove \$\displaystyle <g^k> = <g^d>\$.

now k = db, so \$\displaystyle g^k = g^{db} = (g^d)^b\$ therefore:

\$\displaystyle <g^k> \subseteq <g^d>\$

writing d = ns + kt (which we can by the euclidean algorithm), we have:

\$\displaystyle g^d = g^{ns+kt} = (g^{ns})(g^{kt}) = (g^n)^s(g^k)^t = (g^k)^t\$

so we also know that

\$\displaystyle <g^d> \subseteq <g^k>\$

so \$\displaystyle <g^k> = <g^d>\$. this means that \$\displaystyle |g^k| = |g^d|\$.

now obviously \$\displaystyle (g^d)^{n/d} = e\$. suppose that \$\displaystyle (g^d)^u = e\$

for some 0 < u < n/d. then 0 < du < n, but \$\displaystyle g^{du} = (g^d)^u = e\$

contradicting the fact that the order of g is n. thus there can be no such u,

so \$\displaystyle |g^k| = |g^d| = n/d\$.