Orders and primitive roots

Euler's theorem says $a^{\varphi(n)}\equiv1$. The finer question is the least such exponent, and whether some $a$ achieves the maximum $\varphi(n)$: then $(\mathbb{Z}/n)^\times$ is cyclic.

1. Order (Def. 1.1, Lemma 1.2, Prop. 1.3) and the totient sum (Lemma 1.4).
2. Lagrange's theorem on roots (Thm 1.5) and primitive roots modulo $p$ (Thm 1.6), with a test (Prop. 1.7).
3. Hensel's lemma (Thm 1.8), primitive roots modulo $p^k$ (Thm 1.9) and the structure of $(\mathbb{Z}/n)^\times$ (Cor. 1.10).
4. Discrete logarithms (Example 1.11).

For $\gcd(a, n) = 1$, the order $\operatorname{ord}_n(a)$ is the least $k\ge1$ with $a^k\equiv1\pmod n$. It exists by Euler's theorem, and it is the order of $a$ in the group $(\mathbb{Z}/n)^\times$. A primitive root mod $n$ is an $a$ with $\operatorname{ord}_n(a) = \varphi(n)$.

$a^m\equiv1\pmod n$ if and only if $\operatorname{ord}_n(a)\mid m$. In particular $\operatorname{ord}_n(a)\mid\varphi(n)$, and $a^i\equiv a^j$ iff $i\equiv j\pmod{\operatorname{ord}_n(a)}$.

If $\operatorname{ord}_n(a) = d$ then $\operatorname{ord}_n(a^k) = \frac d{\gcd(d, k)}$. In particular if $g$ is a primitive root mod $n$, then $g^k$ is a primitive root iff $\gcd(k, \varphi(n)) = 1$, so there are $\varphi(\varphi(n))$ primitive roots.

For every $n\ge1$, $\displaystyle\sum_{d\mid n}\varphi(d) = n$.

A non-zero polynomial of degree $d$ over $\mathbb{Z}/p$ has at most $d$ roots mod $p$. Consequently, if $d\mid p - 1$ then $x^d - 1$ has exactly $d$ roots mod $p$.

For every prime $p$, $(\mathbb{Z}/p)^\times$ is cyclic: there is a primitive root $g$. More precisely, for each $d\mid p - 1$ there are exactly $\varphi(d)$ elements of order $d$.

Let $p$ be prime and $\gcd(g, p) = 1$. Then $g$ is a primitive root mod $p$ if and only if $g^{(p-1)/q}\not\equiv1\pmod p$ for every prime $q\mid p - 1$.

Let $f\in\mathbb{Z}[x]$, $k\ge1$, and $f(a)\equiv0\pmod{p^k}$ with $f'(a)\not\equiv0\pmod p$. Then there is a unique $t$ mod $p$ such that $b = a + tp^k$ satisfies $f(b)\equiv0\pmod{p^{k+1}}$, namely $t\equiv-\frac{f(a)}{p^k}f'(a)^{-1}\pmod p$. Iterating, a simple root mod $p$ lifts uniquely to a root mod every $p^k$.

Primitive roots mod $n$ exist exactly for $n = 1, 2, 4, p^k$ and $2p^k$ ($p$ an odd prime, $k\ge1$). If $g$ is a primitive root mod $p$ with $g^{p-1}\not\equiv1\pmod{p^2}$ (replacing $g$ by $g + p$ if necessary), then $g$ is a primitive root mod every $p^k$.

If $n = 2^ep_1^{k_1}\cdots p_r^{k_r}$ then $(\mathbb{Z}/n)^\times\cong(\mathbb{Z}/2^e)^\times\times\prod_iC_{(p_i - 1)p_i^{k_i - 1}}$, where $(\mathbb{Z}/2)^\times$ is trivial, $(\mathbb{Z}/4)^\times\cong C_2$, and $(\mathbb{Z}/2^e)^\times = \langle-1\rangle\times\langle5\rangle\cong C_2\times C_{2^{e-2}}$ for $e\ge3$.

Fix a primitive root $g$ mod $p$. The index (discrete logarithm) $\operatorname{ind}_g(a)$ is the $k$ mod $p - 1$ with $g^k\equiv a$. It turns multiplication into addition: $x^m\equiv a$ becomes $m\operatorname{ind}x\equiv\operatorname{ind}a\pmod{p - 1}$, which is solvable iff $\gcd(m, p - 1)\mid\operatorname{ind}a$, with $\gcd(m, p - 1)$ solutions. Computing indices is believed hard for large $p$, which underlies Diffie–Hellman key exchange: from $g^a$ and $g^b$ both parties compute $g^{ab}$.

• Orders divide $\varphi(n)$: only test divisors.
• Primitive root mod $p$: check $g^{(p-1)/q}\ne1$ for primes $q\mid p - 1$ (fast by repeated squaring).
• Modulus has a primitive root only if $n = 1, 2, 4, p^k, 2p^k$.
• Power congruences mod $p$: count solutions with $\gcd(m, p - 1)$.
• Lifting to $p^k$: Hensel, if $f'(a)\not\equiv0$.