Multiplicative Order Divides Every Valid Exponent

The order of a unit modulo n divides the group exponent and any positive exponent returning it to one. A small computation will anchor the general statement before the abstraction takes over.

Statement

Congruences turn divisibility into arithmetic in $\mathbf Z/n\mathbf Z$. The unit group $(\mathbf Z/n\mathbf Z)^\times$ controls which residues can be cancelled, inverted, or assigned a multiplicative order.

$$ \operatorname{ord}_n(a)=\min\{r\ge1:a^r\equiv1\pmod n\} $$

The definition determines which expressions are legal; only then does the identity become meaningful. An equality in $\mathcal A$ may change ambient meaning, so I keep $\mathsf D$ separate from $\mathsf C$.

$$ a^m\equiv1\pmod n\Longleftrightarrow\operatorname{ord}_n(a)\mid m $$

Worked algebra

Here is a concrete symbolic test. Reading it from left to right reveals which transformation is reversible and which is only an implication.

$$ \begin{array}{c|rrrrrr}k&1&2&3&4&5&6\\\hline3^k\bmod7&3&2&6&4&5&1\end{array}\qquad\operatorname{ord}_7(3)=6 $$

Conceptual compression

The invariant statement is the one that does not depend on a convenient choice of coordinates, representatives, basis, or enumeration.

$$ \begin{aligned} \mathsf{D}\;&:\quad \operatorname{ord}_n(a)=\min\{r\ge1:a^r\equiv1\pmod n\},\\[5pt] \mathsf{C}\;&:\quad a^m\equiv1\pmod n\Longleftrightarrow\operatorname{ord}_n(a)\mid m. \end{aligned} $$

Caveat

Cancellation modulo $n$ requires a unit. Dividing both sides by a zero divisor is one of the fastest ways to manufacture a false congruence.

$$ \boxed{\begin{gathered} \text{compact conclusion}\\[-2pt] a^m\equiv1\pmod n\Longleftrightarrow\operatorname{ord}_n(a)\mid m \end{gathered}} $$

The final box is a summary, not a new assumption; the proof still lives in the definitions and the intervening calculation. The source keeps each scope delimiter visible for later inspection.

This article was posted on Mon 09 March 2015. Facts and circumstances may have changed since publication.
Please contact me before jumping to conclusions if something seems wrong or unclear.

Multiplicative Order Divides Every Valid Exponent by Vicfred

Statement

Worked algebra

Conceptual compression

Caveat