Prove that the order of any element in the additive group of integers modulo n is a divisor of n.

I have been on and off of this problem for three days and need to present the proof tomorrow. I am thinking that because I know for any element in the additive group of integers modulo n the order for that element is the ratio of n and the greatest common factor of that element and n then I can say,[...chirp, chirp, chirp...] and my mind goes blank. What can I say? I have also tried using the division algorithm to say the order of any element in the group can be written as a multiple of n and some other integer but I am coming up blank. There is something I do not fully understand and would like for you to point out my oversight. Thanks.

• Lol, "chirp chirp." You're funny! – Shine On You Crazy Diamond Oct 31 '13 at 0:57
• This is just a direct application of Lagrange's theorem. – lhf Oct 31 '13 at 0:59

$\Bbb Z_n$ is a group and thus if $a\in \Bbb Z_n$ then $<a>$ is a cyclic subgroup of $\Bbb Z_n$ with order equal to the order of the element $a$. By Lagrange's Theorem we have that $|\Bbb Z_n|=[\Bbb Z_n:<a>]|<a>|$ and thus $|<a>||n$

Let $H$ be a subgroup of $G$. Let's count the cosets of $H$. They partition G. Look that up and see what it means. And there's a bijection between any two. Proof that. I'll wait...

okay. So there's a bijection between $H$ and any other coset $aH$, therefore there are $k$ cosets of size $|H|$ (the size of the set $H$ sometimes called order of $H$ ), and since they partition $G$ you have $|H|k = |G|$. $k$ is usually denoted $[G : H]$ and called the index of $H$ in $G$. It's equal to the size of the group $G/H$ when $H$ is normal.

So apply this result to any subgroups of $G$ including the cyclic ones you generate when you continually add an element to itself: $a, 2a, 3a, ..., na = 0$, so $n$ the order is equal to the size of that cyclic subgroup $H$. Apply theorem above.

Let $G$ be any finite group and $g\in G$, $g\not=e$. Then the sequence $\{g^n\}_{n=1}^\infty$ is an infinite subset of $G$ and it also is a subgroup of $G$. Since the group $G$ is finite, there must be integers $m$ and $n$ so that $g^m = g^n$. Hence there is a positive power $p$ so that $g^p = e$. The least such power is the order of $g$, and it is the order of the subgroup of $g$ defined by this sequence.

But the order of any subgroup of a finite group divides the order of the entire group. Hence $o(g)\,\, |\,\, |G|$.

Let the order of our element $a$ be $m$. That means that $ma$ ($a$ added to itself $m$ times) is divisible by $n$, and there is no positive integer $k\lt m$ such that $n$ divides $ka$.

By the Division Algorithm, we have $$n=qm+r$$ for some $r$, where $0\le r\lt m$.

Thus $na=q(ma)+ra$. Since $ma$ is divisible by $n$, we have that $n$ divides $q(ma)$, and therefore $n$ divides $ra$.

Thus $a$ added to itself $r$ times is the $0$-element of the group. If $r\gt 0$, that contradicts the fact that $a$ has order $m$, since $m$ is the smallest positive integer such that $ma$ is the $0$-element of the group.

Thus $r=0$, and therefore $n=qm$, meaning that $m$ divides $n$.