Euler's theorem says $a^{\varphi(n)} \equiv 1$, so the powers of a unit $a$ eventually come back to 1. But often they come back sooner: mod 7, $2^{3} = 8 \equiv 1$, long before $2^{6}$. The first return time is the most useful single number about $a$.
Definition. If $\gcd(a, n) = 1$, the order of $a$ mod $n$, written $\operatorname{ord}_n(a)$, is the smallest $k > 0$ with $a^{k} \equiv 1 \pmod{n}$.
Theorem. Let $k = \operatorname{ord}_n(a)$. Then $a^{m} \equiv 1 \pmod{n}$ exactly when $k \mid m$. In particular $k \mid \varphi(n)$, and the powers of $a$ repeat with period exactly $k$.
Why it works
Worked example: By listing powers
- $2^{1} = 2$, $2^{2} = 4$, $2^{3} = 8 \equiv 1 \pmod{7}$.
- The first power that is 1 is the third.
Answer: $\operatorname{ord}_7(2) = 3$.
Worked example: Testing only divisors
- The order divides $\varphi(13) = 12$, so it is one of $1, 2, 3, 4, 6, 12$.
- $5^{1} = 5$. $5^{2} = 25 \equiv 12 \equiv -1$. $5^{3} \equiv 5 \cdot 12 = 60 \equiv 8$.
- $5^{4} = (5^{2})^{2} \equiv (-1)^{2} = 1$. So the order is $4$.
Answer: $4$.
Worked example: Order of a power
- $(2^{8})^{m} = 2^{8m} \equiv 1$ exactly when $12 \mid 8m$, that is, when $3 \mid 2m$, that is, when $3 \mid m$.
- So the order is $3 = \dfrac{12}{\gcd(12, 8)}$. Check: $2^{8} = 256 \equiv 9$, and $9^{3} = 729 = 56 \cdot 13 + 1$.
Answer: $3$.
The last example is a general rule: if $\operatorname{ord}_n(a) = k$, then $\operatorname{ord}_n(a^{j}) = \dfrac{k}{\gcd(k, j)}$.
Orders explain repeating decimals. The decimal of $\frac{1}{7} = 0.\overline{142857}$ repeats every 6 digits because $\operatorname{ord}_7(10) = 6$: the first $k$ with $7 \mid 10^{k} - 1$ is $k = 6$, since $999{,}999 = 7 \cdot 142{,}857$. In general, for $p \ne 2, 5$, the period of $\frac{1}{p}$ is $\operatorname{ord}_p(10)$, so it always divides $p - 1$.
Common mistake
Key idea