9
$\begingroup$

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?

$\endgroup$
9
$\begingroup$

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

$\endgroup$
10
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Bernard Aug 31 '18 at 17:39
  • $\begingroup$ 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$. $\endgroup$ – BCLC Aug 31 '18 at 17:46
  • 1
    $\begingroup$ It might be used. However, I wonder whether the notion of order of an element doesn't ultimately on Lagrange's theorem. $\endgroup$ – Bernard Aug 31 '18 at 19:12
  • $\begingroup$ Thanks Bernard! $\endgroup$ – BCLC Aug 31 '18 at 19:17
2
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.