# Proof involving Cyclic group, generator and GCD

Theorem: $$\left\langle a^k \right\rangle = \left\langle a^{\gcd(n,k)}\right\rangle$$ Let G be a group and $$a \in G$$ such that $$|a|=n$$ Then:

$$\left\langle a^k \right\rangle = \left\langle a^{\gcd(n,k)}\right\rangle$$

The proof begins by letting d = gcd(n,k) such that d is a divisor of k so there exists an integer r such that k = dr. So, $$a^k=(a^d)^r$$.

$$\left\langle a^k \right\rangle \subseteq \left\langle a^{\gcd(n,k)}\right\rangle$$

I've spent a very long time on understanding this proof but found it to be obscure. I suspect there are some gaps in my understanding. If someone could show me the light I'll be really glad. I do not understand why the exponent r on a 'vanishes'.

Secondly, how does $$a^k\in \left\langle a^d\right\rangle$$ follows?

Thirdly, where does closure plays a role?

• It has been edited but the nature of my question remains unchanged.
– user
May 29, 2015 at 11:46
• Do you know Bézout's theorem that if $\gcd(a,n) = 1$, then there exists an integer $b$ such that $ab\equiv 1 \pmod n$? May 29, 2015 at 11:49
• With $|a|$, do you mean the order of $a$ with respect to the group $G$ ? May 29, 2015 at 11:49
• @Peter I have. If it were $$a^k=a^r$$, I would have no problem since I can exploit the division algorithm. and show that $$a^k$$ is in the cyclic group generated by the element.
– user
May 29, 2015 at 11:49
• @Peter Yes, that was what I meant.
– user
May 29, 2015 at 11:51

## 2 Answers

Given an element $a$ of a group $G$, $\langle a\rangle$ is by definition the smallest subgroup of $G$ which contains $a$. This means in particular that if $H$ is a subgroup of $G$ which contains $a$, then $\langle a\rangle \subseteq H$.

Here, you want to prove two statements of this form (for ease of notation, I let $d = \gcd(n,k)$):

1. You want to prove that $\langle a^k\rangle \subseteq \langle a^d\rangle$. From the preceeding discussion, this is the same thing as proving that $a^k \in \langle a^d\rangle$, which in turn means that there is some $e$ such that $a^k = \left(a^d\right)^e$.
2. Conversely, you want to prove that $\langle a^d\rangle \subseteq \langle a^k\rangle$, this is the same thing as $a^d \in \langle a^k\rangle$.

The first one is easy: $d$ is by definition a divisor of $k$, so there exists an integer $e$ such that $k = de$. But then $\left(a^d\right)^e = a^{de} = a^k$ so $a^k \in \langle a^d\rangle$.

For the second one, you have to know that if $\gcd(n,k) = d$, then there exists an integer $\ell$ such that $k\ell \equiv d\pmod n$, meaning that there exists an integer $m$ such that $k\ell = d + mn$. Then $$\left(a^k\right)^\ell = a^{k\ell} = a^{d+mn} = a^da^{mn} = a^d\underbrace{\left(a^n\right)}_{=1}{}^m = a^d,$$ so $a^d \in \langle a^k\rangle$.

• I apologise but this is very frustrating especially having stayed awake for more than 14 hrs. Given $$a^k$$, I know that by the division algo, we have $$a^k=a^(qn+r)=(a^n)^q=ea^r=a^r$$ And since r is between 0 and n, we have $$a^k$$ lying in the group generated by the element a.
– user
May 29, 2015 at 12:24
• But how is $$a^k=(a^d)^e$$?
– user
May 29, 2015 at 12:25
• You might really have to spell it out.
– user
May 29, 2015 at 12:28
• I don't understand what you are trying to say. Since $k = de$, certainly $a^k = a^{de} = \left(a^d\right)^e$, no? May 29, 2015 at 12:31
• shouldn't it be k=dr? Assuming you were using a different form, why is r = e in this case?
– user
May 29, 2015 at 12:33

for the converse part

since $d=gcd(n,k)$ and therefore from $euclidian~ algorithem$ there exists

integers $s~\&~t$ such that

$ns+kt=d$

This will imply that $a^d=a^{ns+kt}$

$\implies a^d=(a^n)^s (a^k)^t$

$\implies a^d=(a^k)^t$ since $|a|=n$

$\implies a^d \in <a^k>$

So combining equalities you'll get required thing

• This does not answer my problem. My issue is still with 1) how the last sentence followed from the second last. 2)closure
– user
May 29, 2015 at 11:59
• I am not able to know where you have confusion. Specify clearly May 29, 2015 at 12:02
• 1)How does $$\left.a^k\text{=(}a^d)^r\text{\to  }a^k\in \langle a^d\right\rangle$$ 2)How does $$\left\langle a^k\text{\rangle \backslash \backslash subset\langle }a^{\gcd (n,k)}\right\rangle$$ follows from closure?
– user
May 29, 2015 at 12:08
• This is basic cyclic group's result. May 29, 2015 at 12:13