Integer to Power of Multiple of Order

Theorem

Let $a$ and $n$ be integers.

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

Then $a^k \equiv 1 \pmod n$ iff $k$ is a multiple of $c$.

Further, $\phi \left({n}\right)$ is a multiple of $c$, where $\phi \left({n}\right)$ is the Euler phi function of $n$.

Proof

• Let $k$ be a multiple of $c$.

Then $k = cr$, say.

Then:

$a^k = a^{cr} = \left({a^c}\right)^r \equiv 1^r \equiv 1 \pmod n$

• Let $a^k \equiv 1 \pmod n$.

Then:

$1 \equiv a^k \equiv a^{q c + r} \equiv \left({a^c}\right)^q a^r \equiv 1^q a^r \equiv a^r \pmod n$

So $r = 0$ or else (from the Division Theorem) $0 < r < c$ and this contradicts $c$ being the smallest integer such that $a^c \equiv 1 \pmod n$.

Hence $k$ is a multiple of $c$.

$\blacksquare$

From Euler's Theorem, we have $a^{\phi \left({n}\right)} \equiv 1 \pmod n$ and the above result can be applied directly.

$\blacksquare$