Back to the on-screen lesson ·
The first exponent that returns a residue to one, why it divides the totient, and the residues whose powers reach everything.
Paper packet. Every task here also exists on screen, where it is checked automatically; answers written on paper are not assessed by Nydus. When you are back at a device, enter your answers there.
By the end of this lesson you will be able to compute the order of a residue by testing only the divisors of the totient, prove that every exponent returning a residue to one is a multiple of its order, decide whether a residue is a primitive root with one test per prime factor, say how many primitive roots a prime modulus has and which moduli have any at all, and read a small table of discrete logarithms.
Euler's theorem says $a^{\varphi(n)} \equiv 1$ for a unit $a$. It never claimed that exponent was the smallest, and lesson 13's worked example already showed it need not be: modulo $15$, $\varphi(15) = 8$, and yet $7^{4} \equiv 1$ already.
So there are two numbers in play — the exponent the theorem hands over and the first exponent that actually works — and they are usually different. This lesson is about the second one. It turns out to divide the first, which is what makes it findable, and the residues for which the two agree are special enough to have a name.
The order of a unit $a$ modulo $n$, written $\operatorname{ord}_n(a)$, is the smallest positive $k$ with $a^{k} \equiv 1 \pmod n$.
A primitive root modulo $n$ is a unit whose order is $\varphi(n)$ — the largest it can be. Its powers then run through every unit before returning to $1$.
A group of units with a primitive root is cyclic: one element generates it. Modulo a prime the units are always cyclic; modulo $8$ they are not.
The discrete logarithm of $b$ to base $g$ modulo $p$ is the exponent $k$ with $g^{k} \equiv b$. It exists for every unit exactly when $g$ is a primitive root.
The key lemma. $a^{k} \equiv 1 \pmod n$ if and only if $\operatorname{ord}_n(a) \mid k$.
Proof: write $k = qd + r$ with $d$ the order and $0 \le r < d$. Then $1 \equiv a^{k} = (a^{d})^{q}a^{r} \equiv a^{r}$, and $r < d$ forces $r = 0$ by minimality of $d$. The converse is immediate.
Consequence. Since $a^{\varphi(n)} \equiv 1$, the order divides $\varphi(n)$ — and modulo a prime, divides $p - 1$. That is what makes an order computable: only the divisors of $p-1$ need testing, so a few exponentiations settle it however large the prime.
Powers of a residue. $\operatorname{ord}(a^{k}) = \dfrac{d}{\gcd(k, d)}$ where $d = \operatorname{ord}(a)$. So raising to a power never increases the order, and preserves it exactly when $\gcd(k, d) = 1$.
Primitive roots exist modulo every prime. The proof counts: for each divisor $d$ of $p-1$, the residues of order $d$ number either $0$ or $\varphi(d)$, because they would all be roots of $x^{d} - 1$, which modulo a prime has at most $d$ roots. Since $\sum_{d \mid p-1}\varphi(d) = p-1$ and the counts must add to $p-1$, none of them can be $0$. In particular there are $\varphi(p-1)$ primitive roots.
That is a pure existence argument. It produces no primitive root and no bound on where the smallest one is; finding one is done by trying $2, 3, 5, \ldots$ and testing, which works quickly in practice and is not known to be guaranteed.
Which moduli have one at all. Only $1, 2, 4, p^{k}$ and $2p^{k}$ for odd primes $p$. Modulo $8$ every unit squares to $1$, so the largest order is $2$ while $\varphi(8) = 4$: no generator.
Another way: steps
Another way: example
Modulo $13$, with $p - 1 = 12$. Is $2$ a primitive root? The primes dividing $12$ are $2$ and $3$, so test $2^{6} = 64 \equiv 12$ and $2^{4} = 16 \equiv 3$. Neither is $1$, so the order is not a proper divisor of $12$ and $2$ is a primitive root. Two exponentiations, not twelve. And $3$: $3^{3} = 27 \equiv 1$, so its order is $3$ and it is not.
Fix a primitive root $g$ modulo $p$. Every non-zero residue is $g^{k}$ for exactly one $k$ in $\{1, \ldots, p-1\}$, and that $k$ is the discrete logarithm of the residue.
The map $k \mapsto g^{k}$ therefore converts addition modulo $p-1$ into multiplication modulo $p$, exactly as an ordinary logarithm converts addition into multiplication. In modern language: the units modulo $p$ form a cyclic group of order $p-1$, isomorphic to $\mathbb{Z}_{p-1}$ under addition.
That single sentence answers several questions at once, and the answers are all counting answers with no computation in them.
How many residues have order $d$? The residue $g^{k}$ has order $(p-1)/\gcd(k, p-1)$, so order $d$ requires $\gcd(k, p-1) = (p-1)/d$ — and there are $\varphi(d)$ such $k$. So exactly $\varphi(d)$ residues for each divisor $d$ of $p-1$, and none for a non-divisor.
Which residues are squares? $g^{k}$ is a square exactly when $k$ is even, so exactly half of them — $(p-1)/2$. That fact is the whole of the next lesson, and it is visible here before any quadratic notation is introduced.
When is $x^{m} \equiv b$ solvable? Taking logarithms it becomes $mk \equiv \log b \pmod{p-1}$, a linear congruence — which lesson 8 solved completely. Solvable exactly when $\gcd(m, p-1)$ divides $\log b$, with that many solutions.
So a primitive root converts hard-looking multiplicative questions into linear congruences. The catch is that using it needs the discrete logarithm, and computing that for a large prime is exactly the problem nobody can do quickly. The structure is perfectly understood and the map into it is not efficiently computable — which is an unusual situation, and the one a key exchange is built on.
Taking any exponent that works as the order. $a^{p-1} \equiv 1$ always; the order is the first exponent that does. Modulo $7$, $2^{6} \equiv 1$ and also $2^{3} \equiv 1$, so the order is $3$.
Testing every exponent. Only divisors of $p-1$ can be orders, so only those need testing. For $p - 1 = 100$ that is nine tests rather than a hundred.
Assuming every modulus has a primitive root. Only $1, 2, 4, p^{k}$ and $2p^{k}$ do. Modulo $8$ or modulo $12$ there is no generator, and arguments that assume one are simply false there.
Expecting a formula for the smallest primitive root. There is none. The existence proof is a counting argument and constructs nothing; searching from $2$ upwards is what is done, and its speed is conjectural rather than proved.
Confusing the two moduli again. The residue lives modulo $p$; its discrete logarithm lives modulo $p-1$. Multiplying residues adds logarithms modulo $p-1$, and forgetting that is the commonest slip once logarithms are in use.
Find the order of $5$ modulo $23$. Here $p - 1 = 22$, whose divisors are $1, 2, 11, 22$.
Four candidates, not twenty-two.
$5^{1} = 5 \ne 1$. $5^{2} = 25 \equiv 2 \ne 1$. $5^{11}$: build it as $5^{8} \cdot 5^{2} \cdot 5$, with $5^{4} \equiv 4$ and $5^{8} \equiv 16$, giving $16 \cdot 2 \cdot 5 = 160 \equiv 22$.
Square-and-multiply keeps each test cheap.
$22 \equiv -1 \ne 1$, so no proper divisor works and the order is $22$: $5$ is a primitive root modulo $23$.
Three tests settled it.
Modulo $8$ the units are $\{1, 3, 5, 7\}$, so $\varphi(8) = 4$ and a primitive root would have order $4$.
What a generator would have to do.
But $3^2 = 9 \equiv 1$, $5^2 = 25 \equiv 1$ and $7^2 = 49 \equiv 1$. Every unit has order at most $2$.
Three squarings exhaust the possibilities.
So no unit generates the group, and the units modulo $8$ are not cyclic. This is why the theorem is stated for primes and prime powers of odd primes, and why $2^{k}$ for $k \ge 3$ is the exception.
The hypothesis on the modulus is doing real work.
Let $d$ be the order of $a$, and use $\operatorname{ord}(a^{k}) = d/\gcd(k, d)$ with $k = 2$.
The formula does the whole job.
If $d$ is odd then $\gcd(2, d) = 1$.
Oddness is the only place the hypothesis enters.
So the order of $a^{2}$ is $d/1 = d$. When $d$ is even it halves instead, which is why squaring a primitive root modulo an odd prime never gives another one.
Working modulo $13$, give the order of each residue — the smallest positive exponent that brings it back to $1$.
| Order | |
|---|---|
| $12$ | |
| $4$ | |
| $11$ |
What is the order of $5$ modulo $11$?
Answer:
Is $12$ a primitive root modulo $17$?
Modulo the prime $19$, give the order that a primitive root has, and how many primitive roots there are.
order a, how many c
Working modulo $13$, match each residue to its order.
| $2$ | $6$ | $12$ | |
|---|---|---|---|
| $12$ | |||
| $4$ | |||
| $11$ |
$3$ is a primitive root modulo $17$, so every non-zero residue is a power of it. For each residue below, give the exponent between $1$ and $16$ that produces it.
| Exponent | |
|---|---|
| $2$ | |
| $3$ | |
| $4$ |
Lesson test: one question per skill, one attempt each, no hints. Your answers are checked when you submit.
Working modulo $23$, give the order of each residue — the smallest positive exponent that brings it back to $1$.
| Order | |
|---|---|
| $22$ | |
| $18$ | |
| $21$ |
You can find the order of any residue and decide whether it generates all the others. Say in your own words why only the divisors of one less than the prime need testing. Next: which residues are squares.
9. Your turn: show that the order of $a^{2}$ is the order of $a$ when that order is odd, step 3