Multiplicative order

Definition

Let $n$ be a positive integer and let $a$ be an integer coprime to $n$. The multiplicative order of $a$ modulo $n$ is the smallest positive integer $k$ such that $a^k \equiv 1 \pmod n$. The notation for it is $\operatorname{ord}_n(a)$.

Remarks

The order exists, because $a^{\varphi(n)} \equiv 1 \pmod n$ by Euler's theorem. For each integer $m \ge 0$, $a^m \equiv 1 \pmod n$ if and only if $\operatorname{ord}_n(a) \mid m$. In particular, $\operatorname{ord}_n(a) \mid \varphi(n)$. The order of $a$ modulo $n$ is the order of $\overline{a}$ in the group $(\mathbb{Z}/n\mathbb{Z})^\times$. For example, $\operatorname{ord}_7(2) = 3$, because $2^1 = 2$, $2^2 = 4$ and $2^3 = 8 \equiv 1 \pmod 7$.

Explanations

L1 human

Compute the powers $a, a^2, a^3, \dots$ modulo $n$, until you reach $1$. The number of steps is the order. Modulo $10$, the powers of $3$ are $3, 9, 7, 1$, so the order of $3$ modulo $10$ is $4$.