2
$\begingroup$

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?

$\endgroup$
6
  • $\begingroup$ It has been edited but the nature of my question remains unchanged. $\endgroup$
    – user
    May 29, 2015 at 11:46
  • 1
    $\begingroup$ 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$? $\endgroup$
    – fkraiem
    May 29, 2015 at 11:49
  • $\begingroup$ With $|a|$, do you mean the order of $a$ with respect to the group $G$ ? $\endgroup$
    – Peter
    May 29, 2015 at 11:49
  • $\begingroup$ @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. $\endgroup$
    – user
    May 29, 2015 at 11:49
  • $\begingroup$ @Peter Yes, that was what I meant. $\endgroup$
    – user
    May 29, 2015 at 11:51

2 Answers 2

3
$\begingroup$

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$.

$\endgroup$
6
  • $\begingroup$ 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. $\endgroup$
    – user
    May 29, 2015 at 12:24
  • $\begingroup$ But how is $$a^k=(a^d)^e$$? $\endgroup$
    – user
    May 29, 2015 at 12:25
  • $\begingroup$ You might really have to spell it out. $\endgroup$
    – user
    May 29, 2015 at 12:28
  • $\begingroup$ I don't understand what you are trying to say. Since $k = de$, certainly $a^k = a^{de} = \left(a^d\right)^e$, no? $\endgroup$
    – fkraiem
    May 29, 2015 at 12:31
  • $\begingroup$ shouldn't it be k=dr? Assuming you were using a different form, why is r = e in this case? $\endgroup$
    – user
    May 29, 2015 at 12:33
0
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ This does not answer my problem. My issue is still with 1) how the last sentence followed from the second last. 2)closure $\endgroup$
    – user
    May 29, 2015 at 11:59
  • $\begingroup$ I am not able to know where you have confusion. Specify clearly $\endgroup$ May 29, 2015 at 12:02
  • $\begingroup$ 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? $\endgroup$
    – user
    May 29, 2015 at 12:08
  • $\begingroup$ This is basic cyclic group's result. $\endgroup$ May 29, 2015 at 12:13

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .