Math Core

Euler's theorem says $a^{\varphi(n)} \equiv 1 \pmod n$ , but powers of $a$ often return to $1$ much sooner. The order of $a$ is the exact length of that cycle. Orders explain how long repeating decimals are, which primes can divide numbers like $2^{29} - 1$ or $n^4 + 1$ , and how many solutions $x^k \equiv 1$ has. They drive many of the hardest AIME number theory problems.

Order

Definition

Order

If $\gcd(a, n) = 1$ , the order of $a$ modulo $n$ , written $\operatorname{ord}_n(a)$ , is the smallest positive integer $d$ with $a^d \equiv 1 \pmod n$ .

For example, mod $7$ the powers of $2$ are $2, 4, 1, 2, 4, 1, \dots$ , so $\operatorname{ord}_7(2) = 3$ . The powers of $3$ are $3, 2, 6, 4, 5, 1$ , so $\operatorname{ord}_7(3) = 6$ .

The order divides every exponent that gives 1

Let $d = \operatorname{ord}_n(a)$ . Then

$a^k \equiv 1 \pmod n \iff d \mid k.$

In particular $d \mid \varphi(n)$ , and for a prime $p$ , $d \mid p - 1$ .

Proof. If $d \mid k$ , then $a^k = (a^d)^{k/d} \equiv 1$ . Conversely, suppose $a^k \equiv 1$ . Divide: $k = qd + r$ with $0 \le r < d$ . Then $1 \equiv a^k = (a^d)^q a^r \equiv a^r$ . Since $r < d$ and $d$ is the smallest positive exponent giving $1$ , $r$ must be $0$ . So $d \mid k$ . Euler's theorem gives $a^{\varphi(n)} \equiv 1$ , so $d \mid \varphi(n)$ .

How to compute an order. The order divides $\varphi(n)$ , so only divisors need checking. Better: $d = m$ exactly when $a^m \equiv 1$ but $a^{m/q} \not\equiv 1$ for every prime $q \mid m$ . For $\operatorname{ord}_{101}(2)$ , you only check $2^{50}$ and $2^{20}$ .

Primitive roots

Definition

Primitive root

$g$ is a primitive root mod $n$ if $\operatorname{ord}_n(g) = \varphi(n)$ . Then the powers $g, g^2, \dots, g^{\varphi(n)}$ run through every residue coprime to $n$ .

Primitive roots mod a prime

Every prime $p$ has a primitive root $g$ . So every nonzero residue mod $p$ is $g^k$ for exactly one $k \in \{1, \dots, p-1\}$ , and

$\operatorname{ord}_p(g^k) = \frac{p-1}{\gcd(k, \, p-1)}.$

Consequences:

For each $d \mid p - 1$ there are exactly $\varphi(d)$ residues of order $d$ . In particular there are $\varphi(p-1)$ primitive roots.
$x^k \equiv 1 \pmod p$ has exactly $\gcd(k, p-1)$ solutions.

Why the formula holds. $(g^k)^m \equiv 1$ iff $(p-1) \mid km$ iff $\dfrac{p-1}{\gcd(k,p-1)} \mid m$ . The smallest such $m$ is $\dfrac{p-1}{\gcd(k, p-1)}$ . The counting facts follow: $g^k$ has order $d$ exactly when $\gcd(k, p-1) = (p-1)/d$ , which happens for $\varphi(d)$ values of $k$ ; and $g^{km} \equiv 1$ iff $(p-1) \mid km$ , which holds for $\gcd(k, p-1)$ values of $m$ .

The existence of a primitive root is a deeper fact (it uses that a polynomial of degree $d$ has at most $d$ roots mod $p$ ); on the AIME you can quote it. Primitive roots also exist mod $p^k$ and $2p^k$ for odd primes $p$ , and mod $2$ and $4$ , but not mod $8$ or mod $1000$ .

Three classic applications

Repeating decimals. If $\gcd(n, 10) = 1$ , the decimal for $\dfrac{1}{n}$ repeats with period exactly $\operatorname{ord}_n(10)$ , because $\dfrac{1}{n} = \dfrac{A}{10^d - 1}$ for an integer $A$ exactly when $n \mid 10^d - 1$ .

Prime factors of $a^q - 1$ . Let $q$ be prime and suppose a prime $p \nmid a - 1$ divides $a^q - 1$ . Then $\operatorname{ord}_p(a)$ divides $q$ and isn't $1$ , so it equals $q$ . Since the order divides $p - 1$ , you get $p \equiv 1 \pmod q$ . For $2^{11} - 1$ , every prime factor is $\equiv 1 \pmod{22}$ (it's odd too). The first candidate, $23$ , works: $2047 = 23 \cdot 89$ .

Prime factors of $a^{2^k} + 1$ . If an odd prime $p$ divides $a^{2^k} + 1$ , then $a^{2^k} \equiv -1$ and $a^{2^{k+1}} \equiv 1$ , so the order is exactly $2^{k+1}$ . Hence $p \equiv 1 \pmod{2^{k+1}}$ .

Orders mod prime powers

If $x \equiv 1 \pmod{p^j}$ exactly (with $p$ odd and $j \ge 1$ ), then $x^p \equiv 1 \pmod{p^{j+1}}$ exactly. (Write $x = 1 + tp^j$ and expand $(1 + tp^j)^p$ ; this is a case of lifting the exponent.) So once you know the order mod $p$ , each extra power of $p$ in the modulus multiplies the order by at most $p$ .

Worked example: Computing an order

Find $\operatorname{ord}_{13}(2)$ .

The order divides $12$ . The maximal proper divisors are $6$ and $4$ . $2^4 = 16 \equiv 3$ and $2^6 = 64 \equiv 12 \equiv -1$ . Neither is $1$ , so the order is $12$ : $2$ is a primitive root mod $13$ .

Worked example: A repeating decimal

How long is the repeating block of $\dfrac{1}{37}$ ?

$10^1 \equiv 10$ , $10^2 \equiv 26$ , $10^3 = 1000 = 27 \cdot 37 + 1 \equiv 1 \pmod{37}$ . So $\operatorname{ord}_{37}(10) = 3$ , and indeed $\dfrac{1}{37} = 0.\overline{027}$ .

Worked example: Factoring with orders

Find the smallest prime factor of $12^4 + 1 = 20737$ .

Any odd prime factor $p$ has $12^4 \equiv -1$ , so $\operatorname{ord}_p(12) = 8$ and $p \equiv 1 \pmod 8$ . And $p \ne 2$ since $20737$ is odd. The primes $\equiv 1 \pmod 8$ are $17, 41, 73, 89, \dots$ Testing: $20737 = 17 \cdot 1219 + 14$ , $20737 = 41 \cdot 505 + 32$ , $20737 = 73 \cdot 284 + 5$ , and $20737 = 89 \cdot 233$ . The answer is $89$ (and $233 \equiv 1 \pmod 8$ too, as it must be).

Worked example: Counting solutions

How many $x \in \{1, 2, \dots, 100\}$ satisfy $x^{20} \equiv 1 \pmod{101}$ ?

With a primitive root $g$ , write $x = g^k$ . Then $x^{20} \equiv 1$ iff $100 \mid 20k$ iff $5 \mid k$ . There are $20$ such $k$ in $1, \dots, 100$ , matching $\gcd(20, 100) = 20$ .

Common mistake

" $a^k \equiv 1$ " tells you the order divides $k$ , not that it equals $k$ . To prove the order is exactly $m$ , you must rule out every $m/q$ for primes $q \mid m$ .