# How to prove $|a^k|=n/\gcd(n,k)$ whenever $|a|=n$?

This is an exercise from "Contemporary Abstract Algebra" I'm not sure how to solve.

Exercise: Let $\langle a\rangle$ be a (cyclic) group of order $n$. Prove that the order of $a^k=\frac{n}{\gcd(n,k)}$.

Direction: (1) Let $d=\gcd(n,k)$, thus by the Euclidian algorithm we can find $X,Y\in\mathbb{Z}$ s.t. $d=Xn+Yk$, thus, $a^d=a^{Xn+Yk}=a^{Xn}a^{Yk}=(a^n)^X(a^k)^Y=(a^k)^Y$. What to do from here?

(2) We know that $d|n$, thus $\langle a^{n/d} \rangle$ is of order $d$ and $\langle a^d \rangle$ is of order $\frac{n}{d}=\frac{n}{\gcd(n,k)}$. Is it mean that $d=k$? Where is my mistake?

You have two things to show. Namely that:

1. $(a^k)^{n/\gcd(n,k)}=e$ (where $e$ denotes the identity)

and that $n/\gcd(n,k)$ is the smallest positive power $p$ of $a^k$ such that $(a^k)^p=e$:

1. For all $m>0$: $(a^k)^m=e \implies n/\gcd(n,k)\leq m$

The first part is easy:

$$(a^k)^{n/\gcd(n,k)}=(a^n)^{k/\gcd(n,k)}=e^{k/\gcd(n,k)}=e$$

For the second part, let $m\in\mathbb{N}$ be such that $(a^k)^m=a^{km}=e$. Since the order of $a$ is $n$, it follows that $n\mid km$. Therefore we also have

$$\frac{n}{\gcd(n,k)}\mid \frac{k}{\gcd(n,k)}m$$

Now $\gcd(n/\gcd(n,k),k/\gcd(n,k))=1$ (try to prove this), so it follows that

$$n/\gcd(n,k)\mid m$$

Hence in particular $n/\gcd(n,k)\leq m$.

• What if $n=25$ and $k=30$? then $\gcd(n/\gcd(n,k),k)=5$. – Silent Jan 24 '18 at 14:39
• @Silent Uncountable should have instead wrote $$n\mid km \implies \frac{n}{g}\mid \frac{k}{g}m\implies \frac{n}{g}\mid m,$$ where $g=\gcd(n,k)$, since $\gcd(n/g,k/g)=1$ is true (while $\gcd(n/g,k)=1$ needn't be). – anon Jan 25 '18 at 6:53
• @anon good one! – Uncountable Jan 25 '18 at 7:58
• – BCLC Aug 31 '18 at 17:08

The order of $a^k$ is the smallest $r>0$ such that $a^{kr}=e$, i.e. such that $kr$ is a multiple of the order $n$ of $a$. This means $kr$ is the least common multiple of $k$ and $n$.

As $\operatorname{lcm}(k,n)=\dfrac{kn}{\gcd(k,n)}$, we have: $\quad r=\dfrac{n}{\gcd(k,n)}.$

• – BCLC Aug 31 '18 at 17:09
• Do you mean corollary 2.8.10? $x^k$ is a element of the group generated by $x$, which has order $n$. But this result is more precise than the corollary. – Bernard Aug 31 '18 at 17:39
• Bernard, interesting, but no. I really mean Cor 2.8.11 intending to use $\gcd(k,p)=1$ for any or all $0 < k < p$. Like somehow we might show that the orders of the non-identity elements are given by $p/\gcd(k,p)$, which of course simplifies to $p$. – BCLC Aug 31 '18 at 17:46
• It might be used. However, I wonder whether the notion of order of an element doesn't ultimately on Lagrange's theorem. – Bernard Aug 31 '18 at 19:12
• Thanks Bernard! – BCLC Aug 31 '18 at 19:17

The proof is a bit simpler if we use basic gcd laws instead of Bézout's identity. Namely

$$(a^{\large k})^{\large j} = 1\iff n\mid kj\iff n\mid nj,kj\iff n\mid(nj,kj)=(n,k)j\iff n/(n,k)\mid j$$

The first $\iff$ follows because $\,n = {\rm\ ord}\, a,\,$ and the third follows by the definition/universal property of the gcd and the gcd distributive law.

Remark $\$ Alternatively, we can use lcm instead of gcd, i.e.

$$(a^{\large k})^{\large j} = 1\iff n\mid kj\iff n,k\mid kj\iff [n,k]\mid kj\iff [n,k]/k\mid j$$

Both proofs are equivalent since $\ [n,k]/k = n/(n,k),\$ i.e. $\ [n,k](n,k) = nk,\,$ by here.

Note that the first equivalence chain implies that $\,a^{\large k}\,$ has order $\,n/(n,k)\,$ since, generally, if $\ b^{\large j} = 1\iff i\mid j\$ then this implies that $\,b\,$ has order $\,i.\,$ Indeed, setting $\,j=i\,$ implies $\,b^{\large i}=1\,$ and $\,i\,$ is the least postive $\,j\,$ with $\,b^{\large j}=1\,$ since $\,i\,$ divides all other such $\,j.\$