Integer has Order Modulo n iff Coprime to n

Theorem

Let $a$ and $n$ be integers.

Let $c \in \Z_+$ be the order of $a$ modulo $n$.

Then $a \perp n$, that is, $a$ and $n$ are coprime.

Proof

By definition, if $c \in \Z_+$ is the order of $a$ modulo $n$, then:

$a^c \equiv 1 \left({\bmod\, n}\right)$

Hence by definition, $a^c = k n + 1$.

Thus $a r + n s = 1$ where $r = a^{c-1}$ and $s = -k$.

The result follows from Integer Combination of Coprime Integers.

$\blacksquare$