Proof of a Property of Element Orders
Problem
Let $a$ be an element in a group $G$. If the order of $a$ is $n$ (i.e., $o(a) = n$), and for some integer $m$ we have $a^m = e$ (where $e$ is the identity), then prove that $n$ must divide $m$ (denoted as $n \mid m$).
Definitions Used
- Order of an Element: The order of an element $a$, denoted $o(a) = n$, is the smallest positive integer $n$ such that $a^n = e$.
- The Division Algorithm: For any integers $m$ and $n$ with $n > 0$, there exist unique integers $q$ (quotient) and $r$ (remainder) such that $m = nq + r$ and $0 \le r < n$.
Proof
We are given that $o(a) = n$ and that $a^m = e$. We want to show that $n \mid m$.
By the Division Algorithm, we can divide $m$ by $n$ to find a unique integer quotient $q$ and a unique integer remainder $r$:
$$ m = nq + r, \quad \text{where } 0 \le r < n $$Now, we use the given fact that $a^m = e$ and substitute our expression for $m$:
$$ a^{nq+r} = e $$Using the rules of exponents for group elements, we can rewrite the left side:
$$ (a^n)^q \cdot a^r = e $$By the definition of the order of $a$, we know that $a^n = e$. Substituting this into our equation gives:
$$ (e)^q \cdot a^r = e $$ $$ e \cdot a^r = e $$ $$ a^r = e $$This result, $a^r = e$, is critical. The Division Algorithm also tells us that the remainder $r$ must be in the range $0 \le r < n$.
However, $n$ is defined as the smallest positive integer for which $a^n = e$. If $r$ were a positive integer less than $n$, it would contradict the definition of $n$. Therefore, the only possibility within the allowed range for $r$ is that $r$ must be 0.
Since $r=0$, our original equation from the Division Algorithm becomes:
$$ m = nq + 0 \quad \implies \quad m = nq $$This shows that $m$ is an integer multiple of $n$. By definition, this means that $n$ divides $m$.
Conclusion
We have successfully shown that if $o(a)=n$ and $a^m=e$, then $n \mid m$.