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 simpler (and more general) if we use basic gcd laws vs. Bezout gcd identity.

$$ (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\qquad$$

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, using notation $\,[x,y] :={\rm lcm}(x,y),$

$$ (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\qquad$$

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

Notice that the equivalences imply $\,a^{\large k}\,$ has order $\,n/(n,k) = [n,k]/k\,$ since, generally, $\ b^{\large j} = 1\iff i\mid j\ $ is equivalent to $\,b\,$ has order $\,i.\,$

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