# Order of an element in a finite cyclic group

Let $G$ be a cyclic group of order $m$ generated by an element $a$. I want to show that the order of $a^k$ is $m/d$, where $d:=\gcd(k,m)$. I have a simple proof, but want to make sure I haven't overlooked anything since the other proofs I've seen (such as in Dummit and Foote) look more complicated.

The order of $a^k$ is the cardinality of the set $\{a^{ks}: s \in \mathbb{Z}\}$, which equals the cardinality of the set $\{a^{ks} a^{mt}: s,t \in \mathbb{Z} \}$ since $a^m$ is the identity. But the set $\{ks+mt: s,t \in \mathbb{Z} \}$ is the set $d \mathbb{Z}$ by the basic properties of integers. So we have that the cardinality of the set is $| \langle a^k \rangle| = |\{1, a^d, a^{2d}, \ldots, a^{m-d} \}| = m/d$.

-
Very nice proof! – lhf Nov 6 '13 at 1:24
Feel free to answer your own question! Even after a period of time, you can accept your own answer. – Clayton Nov 6 '13 at 1:33
That's the shortest proof I've seen of this proposition. Erdos always asked for proofs 'from The Book', and I think you may have found this one. – tylerc0816 Nov 6 '13 at 1:42
In other words: $\langle a^k \rangle = \langle a^{(k,m)} \rangle$, so the claim follows since order of $a^d$ is $m/d$ whenever $d$ divides $m$. – spin Nov 6 '13 at 22:37

As suggested in the comments above, I shall post my proof as an answer:

The order of $a^k$ is the cardinality of the set $\{a^{ks}: s \in \mathbb{Z}\}$, which equals the cardinality of the set $\{a^{ks} a^{mt}: s,t \in \mathbb{Z} \}$ since $a^m$ is the identity. But the set $\{ks+mt: s,t \in \mathbb{Z} \}$ is the set $d \mathbb{Z}$ by the basic properties of integers. So we have that the cardinality of the set is $| \langle a^k \rangle| = |\{1, a^d, a^{2d}, \ldots, a^{m-d} \}| = m/d$.

-