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

4 Answers 4

19
$\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$
4
16
$\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$
5
  • 2
    $\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, 2018 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, 2018 at 17:46
  • 2
    $\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, 2018 at 19:12
  • $\begingroup$ Thanks Bernard! $\endgroup$
    – BCLC
    Aug 31, 2018 at 19:17
2
$\begingroup$

You can think additively in $\Bbb Z/n\Bbb Z$. Say $\bar a$ a generator of $\Bbb Z/n\Bbb Z$, whence $\gcd(a,n)=1$. The order of $k\bar a \in \Bbb Z/n\Bbb Z$ is by definition the least positive integer, say $o(k\bar a)$, such that $o(k\bar a)k\bar a=\bar 0$. But, $o(k\bar a)k\bar a=\overline{o(k\bar a)ka}$, and hence:

\begin{alignat}{1} o(k\bar a)k\bar a=\bar 0 &\iff o(k\bar a)ka \equiv 0 \pmod n \\ &\iff o(k\bar a)ka=mn \end{alignat}

for some $m\in \Bbb Z$. Therefore, the order of $k\bar a$ is the least positive integer of the form ($*$) $\frac{n}{(ka/m)}$, and it is then gotten when the denominator in ($*$) is the greatest divisor of $ka$ which is also divisor of $n$, namely:

\begin{alignat}{1} o(k\bar a) &= \frac{n}{\gcd(ka,n)} \\ &= \frac{n}{\gcd(k,n)} \\ \end{alignat} where the last equality follows from $\gcd(a,n)=1$.

$\endgroup$
1
$\begingroup$

The proof is simpler (and more $\rm\color{darkorange}{general}$) using basic gcd / lcm laws (vs. Bezout gcd identity).

Lemma $\ \ (a^{\large k})^{\large j}\! = 1\color{#90f}{\underset{a^n\,=\,1}\Longleftarrow}\!\!\!\!\!\color{#0a0}{\overset{{\rm ord}\,a\,=\,n}{\Longrightarrow}} n/(n,k)\mid j\,.\ \ $ Proof: $ $ immediate by Euclids Lemma, i.e.

$$ (a^{\large k})^{\large j}\! = 1\color{#90f}{\underset{a^n\,=\,1}\Longleftarrow}\!\!\!\!\!\color{#0a0}{\overset{{\rm ord}\,a\,=\,n}{\Longrightarrow}} n\mid kj\!\iff\! n\mid nj,kj\!\color{#c00}\iff\! n\mid(nj,kj)\!=\!(n,k)j\!\iff\! n/(n,k)\mid j\qquad$$

$\,\color{#0a0}{\rm First\ (\Rightarrow)}\,$ is by $\,n = {\rm\ ord}\, a,\,$ $\rm\color{#c00}{third}$ by the definition/universal property of the gcd and the gcd distributive law. $\,\color{#90f}{\rm Note}$ that the proof of direction $\color{#90f}{(\Leftarrow)}$ needs only $\,\color{#90f}{a^n =1},\,$ not $\,\color{#0a0}{{\rm ord}\,a = n}$.


Alternatively, dually, we can use lcm instead of gcd, using notation $\,[x,y] :={\rm lcm}(x,y),$

$$ (a^{\large k})^{\large j}\! = 1\color{#90f}{\underset{a^n\,=\,1}\Longleftarrow}\!\!\!\!\!\color{#0a0}{\overset{{\rm ord}\,a\,=\,n}{\Longrightarrow}} n\mid kj\iff n,k\mid kj\iff [n,k]\mid kj\iff [n,k]/k\mid j\qquad\qquad$$

Both proofs are equivalent by $\ [n,k]/k = n/(n,k),\ $ i.e. $\ [n,k](n,k) = nk\ $ [gcd $*$ lcm law]


Corollary $\ \ \bbox[5px,border:1px solid #c00]{{\rm ord}(a) = n\,\Rightarrow\,{\rm ord}(a^{\large k}) = \dfrac{n}{(n,k)} = \dfrac{[n,k]}k}\ $ since, generally

$\qquad\qquad\quad\underbrace{ b^{\large j} = 1\iff i\mid j}_{\small \textstyle \text{Lemma has }\, b = a^k}\ $ is equivalent to $\,b\,$ has order $\,i.\,$


$\rm\color{darkorange}{Generality\!\!:}$ proofs using gcd laws (vs. Bezout) apply much more generally, e.g. in UFDs where Bezout fails, e.g. $\,\Bbb Z[x]\,$ and $\,\Bbb Q[x,y],\,$ e.g. $\,(x,2) = 1 = (x,y)\,$ but the gcds cannot be written as linear combinations, else $\, 1 = x\,f(x,y) + y\,g(x,y)\Rightarrow\,1=0\,$ by evaluating at $\,x=0=y.\,$

$\endgroup$

You must log in to answer this question.

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