Olympiad MethodsDifficulty 70-10010 tagged problems

Primitive Roots

Primitive Roots is the habit of using generators of modular multiplication groups to control powers and residues. In contest math, that habit turns a crowded setup into a relation the student can test, bound, count, or compute. MathGrit teaches it as a recognizable signal, a deliberate move, and a final translation back to the original question.

Practice this technique Match my level

The Key Result

$$g \text{ is a primitive root mod } n \iff \operatorname{ord}_n(g) = \varphi(n), \text{ i.e. } \{g^0, g^1, \dots, g^{\varphi(n)-1}\} \equiv (\mathbb{Z}/n\mathbb{Z})^\times.$$

A primitive root mod $n$ is an element whose powers run through every unit mod $n$; such a generator exists exactly when $n$ is $1, 2, 4, p^k,$ or $2p^k$ for an odd prime $p$.

Why It Works

1
By Euler's theorem $g^{\varphi(n)} \equiv 1 \pmod n$ for any unit $g$, so the order $\operatorname{ord}_n(g)$ — the least positive $d$ with $g^d\equiv 1$ — always divides $\varphi(n)$.
2
If that order is the maximum possible, $\varphi(n)$, then the powers $g^0,\dots,g^{\varphi(n)-1}$ are all distinct and hence list every residue coprime to $n$ exactly once.
3
When a primitive root $g$ exists, the multiplicative group $(\mathbb{Z}/n\mathbb{Z})^\times$ is cyclic of order $\varphi(n)$, so every unit is $g^k$ for a unique $k \in \{0,\dots,\varphi(n)-1\}$ — the discrete logarithm.
4
This turns multiplicative questions into additive ones mod $\varphi(n)$: $g^a g^b = g^{a+b}$, so counting solutions of $x^m \equiv c$ reduces to a linear congruence in the exponent.

Worked Examples

Example 1

How many solutions does $x^4 \equiv 1 \pmod{13}$ have?

1
Here $13$ is prime, so $(\mathbb{Z}/13\mathbb{Z})^\times$ is cyclic of order $\varphi(13)=12$ and has a primitive root $g$ (in fact $g=2$ works).
2
Write $x \equiv g^k$. Then $x^4 \equiv 1$ becomes $g^{4k}\equiv g^0$, i.e. $4k \equiv 0 \pmod{12}$.
3
The congruence $4k \equiv 0 \pmod{12}$ has $\gcd(4,12)=4$ solutions for $k$ in $\{0,1,\dots,11\}$, namely $k = 0,3,6,9$.
4
Each distinct exponent gives a distinct residue $x$, so there are exactly $4$ solutions.

Answer:

$4$ solutions.

Contest level

Find the number of primitive roots modulo $13$, and verify $2$ is one of them.

1
If $g$ is one primitive root, every other primitive root is $g^k$ where $\gcd(k, \varphi(13)) = 1$; the count is $\varphi(\varphi(13)) = \varphi(12)$.
2
$\varphi(12) = 12\cdot(1-\tfrac12)(1-\tfrac13) = 12\cdot\tfrac12\cdot\tfrac23 = 4$.
3
Verify $2$ is primitive: its order divides $12$, so it suffices to check $2^{12/q}\not\equiv 1$ for each prime $q\mid 12$ (i.e. $q=2,3$): $2^{6} = 64 \equiv 12 \equiv -1 \not\equiv 1$ and $2^{4} = 16 \equiv 3 \not\equiv 1 \pmod{13}$.
4
Neither is $1$, so $\operatorname{ord}_{13}(2) = 12 = \varphi(13)$; thus $2$ is a primitive root and there are $4$ in total.

Answer:

$4$ primitive roots; $2$ is one of them.

Olympiad / Challenge

Let $p$ be an odd prime. Prove that the product of all primitive roots modulo $p$ is $\equiv 1 \pmod p$ when $p > 3$.

1
Fix a primitive root $g$. The primitive roots are exactly $g^k$ with $\gcd(k, p-1) = 1$, so their product is $g^{S}$ where $S = \sum_{\gcd(k,p-1)=1,\,1\le k\le p-1} k$.
2
The values $k$ coprime to $m = p-1$ pair up as $k \leftrightarrow m - k$ (both coprime to $m$ since $\gcd(m-k,m)=\gcd(k,m)$), each pair summing to $m$. For $m > 2$ these pairings are genuine (no fixed point, since $k = m/2$ is not coprime to $m$), so $S = \tfrac{m}{2}\cdot \varphi(m)$.
3
Because $p > 3$, $m = p-1 > 2$, and $\varphi(m)$ is even for $m > 2$; hence $S = \tfrac{m}{2}\varphi(m)$ is a multiple of $m = p-1$.
4
Therefore $g^{S} \equiv g^{0} \equiv 1 \pmod p$ since $\operatorname{ord}_p(g) = p-1$ divides $S$.

Answer:

The product of all primitive roots is $\equiv 1 \pmod p$ for primes $p > 3$.

Going Deeper

Once a primitive root exists, $(\mathbb{Z}/n)^\times$ is cyclic, so solving $x^m \equiv c$ becomes the linear congruence $m k \equiv \ell \pmod{\varphi(n)}$ in the discrete log — turning multiplicative structure into modular arithmetic.
Primitive roots power AIME/olympiad order and indicator problems (counting $m$-th roots, period lengths of decimal expansions $1/p$, and Artin-style 'is $g$ a generator' questions).
Pitfall: primitive roots exist ONLY for $n = 1, 2, 4, p^k, 2p^k$ (odd prime $p$). Modulo $8$ or $12$ or any other $n$ the group is not cyclic, so 'let $g$ be a primitive root' is simply false there — a frequent fatal assumption.

Spot the Signal

Look for problems where the key step is using generators of modular multiplication groups to control powers and residues.
You can describe the hard part as using generators of modular multiplication groups to control powers and residues, but a direct attack starts producing clutter.
The problem rewards preserving structure instead of expanding, listing, or guessing too early.

Learn the Move

Start by identify the olympiad structure that calls for primitive roots, then rewrite the givens around it.
Name the relation that makes Primitive Roots legal before doing computation.
Use the new relation to replace the messiest part of the problem with a cleaner one.
Translate the result back to the quantity the problem actually asks for.

Avoid These Traps

Do not use Primitive Roots just because the surface looks familiar; verify the required condition first.
Applying Primitive Roots because it sounds relevant, without checking the trigger first.
Stopping after spotting the technique instead of finishing the calculation or proof.

MathGrit Coach Note

Let primitive roots reveal the structural theorem; then compute only what remains.

Try it on:

Practice a contest problem where the key step is using generators of modular multiplication groups to control powers and residues.

Back to techniques

Olympiad MethodsDifficulty 70-10010 tagged problems

Primitive Roots

Practice this technique Match my level

The Key Result

$$g \text{ is a primitive root mod } n \iff \operatorname{ord}_n(g) = \varphi(n), \text{ i.e. } \{g^0, g^1, \dots, g^{\varphi(n)-1}\} \equiv (\mathbb{Z}/n\mathbb{Z})^\times.$$

A primitive root mod $n$ is an element whose powers run through every unit mod $n$; such a generator exists exactly when $n$ is $1, 2, 4, p^k,$ or $2p^k$ for an odd prime $p$.

Why It Works

1
By Euler's theorem $g^{\varphi(n)} \equiv 1 \pmod n$ for any unit $g$, so the order $\operatorname{ord}_n(g)$ — the least positive $d$ with $g^d\equiv 1$ — always divides $\varphi(n)$.
2
If that order is the maximum possible, $\varphi(n)$, then the powers $g^0,\dots,g^{\varphi(n)-1}$ are all distinct and hence list every residue coprime to $n$ exactly once.
3
When a primitive root $g$ exists, the multiplicative group $(\mathbb{Z}/n\mathbb{Z})^\times$ is cyclic of order $\varphi(n)$, so every unit is $g^k$ for a unique $k \in \{0,\dots,\varphi(n)-1\}$ — the discrete logarithm.
4
This turns multiplicative questions into additive ones mod $\varphi(n)$: $g^a g^b = g^{a+b}$, so counting solutions of $x^m \equiv c$ reduces to a linear congruence in the exponent.

Worked Examples

Example 1

How many solutions does $x^4 \equiv 1 \pmod{13}$ have?

1
Here $13$ is prime, so $(\mathbb{Z}/13\mathbb{Z})^\times$ is cyclic of order $\varphi(13)=12$ and has a primitive root $g$ (in fact $g=2$ works).
2
Write $x \equiv g^k$. Then $x^4 \equiv 1$ becomes $g^{4k}\equiv g^0$, i.e. $4k \equiv 0 \pmod{12}$.
3
The congruence $4k \equiv 0 \pmod{12}$ has $\gcd(4,12)=4$ solutions for $k$ in $\{0,1,\dots,11\}$, namely $k = 0,3,6,9$.
4
Each distinct exponent gives a distinct residue $x$, so there are exactly $4$ solutions.

Answer:

$4$ solutions.

Contest level

Find the number of primitive roots modulo $13$, and verify $2$ is one of them.

1
If $g$ is one primitive root, every other primitive root is $g^k$ where $\gcd(k, \varphi(13)) = 1$; the count is $\varphi(\varphi(13)) = \varphi(12)$.
2
$\varphi(12) = 12\cdot(1-\tfrac12)(1-\tfrac13) = 12\cdot\tfrac12\cdot\tfrac23 = 4$.
3
Verify $2$ is primitive: its order divides $12$, so it suffices to check $2^{12/q}\not\equiv 1$ for each prime $q\mid 12$ (i.e. $q=2,3$): $2^{6} = 64 \equiv 12 \equiv -1 \not\equiv 1$ and $2^{4} = 16 \equiv 3 \not\equiv 1 \pmod{13}$.
4
Neither is $1$, so $\operatorname{ord}_{13}(2) = 12 = \varphi(13)$; thus $2$ is a primitive root and there are $4$ in total.

Answer:

$4$ primitive roots; $2$ is one of them.

Olympiad / Challenge

Let $p$ be an odd prime. Prove that the product of all primitive roots modulo $p$ is $\equiv 1 \pmod p$ when $p > 3$.

1
Fix a primitive root $g$. The primitive roots are exactly $g^k$ with $\gcd(k, p-1) = 1$, so their product is $g^{S}$ where $S = \sum_{\gcd(k,p-1)=1,\,1\le k\le p-1} k$.
2
The values $k$ coprime to $m = p-1$ pair up as $k \leftrightarrow m - k$ (both coprime to $m$ since $\gcd(m-k,m)=\gcd(k,m)$), each pair summing to $m$. For $m > 2$ these pairings are genuine (no fixed point, since $k = m/2$ is not coprime to $m$), so $S = \tfrac{m}{2}\cdot \varphi(m)$.
3
Because $p > 3$, $m = p-1 > 2$, and $\varphi(m)$ is even for $m > 2$; hence $S = \tfrac{m}{2}\varphi(m)$ is a multiple of $m = p-1$.
4
Therefore $g^{S} \equiv g^{0} \equiv 1 \pmod p$ since $\operatorname{ord}_p(g) = p-1$ divides $S$.

Answer:

The product of all primitive roots is $\equiv 1 \pmod p$ for primes $p > 3$.

Going Deeper

Once a primitive root exists, $(\mathbb{Z}/n)^\times$ is cyclic, so solving $x^m \equiv c$ becomes the linear congruence $m k \equiv \ell \pmod{\varphi(n)}$ in the discrete log — turning multiplicative structure into modular arithmetic.
Primitive roots power AIME/olympiad order and indicator problems (counting $m$-th roots, period lengths of decimal expansions $1/p$, and Artin-style 'is $g$ a generator' questions).
Pitfall: primitive roots exist ONLY for $n = 1, 2, 4, p^k, 2p^k$ (odd prime $p$). Modulo $8$ or $12$ or any other $n$ the group is not cyclic, so 'let $g$ be a primitive root' is simply false there — a frequent fatal assumption.

Spot the Signal

Look for problems where the key step is using generators of modular multiplication groups to control powers and residues.
You can describe the hard part as using generators of modular multiplication groups to control powers and residues, but a direct attack starts producing clutter.
The problem rewards preserving structure instead of expanding, listing, or guessing too early.

Learn the Move

Start by identify the olympiad structure that calls for primitive roots, then rewrite the givens around it.
Name the relation that makes Primitive Roots legal before doing computation.
Use the new relation to replace the messiest part of the problem with a cleaner one.
Translate the result back to the quantity the problem actually asks for.

Avoid These Traps

Do not use Primitive Roots just because the surface looks familiar; verify the required condition first.
Applying Primitive Roots because it sounds relevant, without checking the trigger first.
Stopping after spotting the technique instead of finishing the calculation or proof.

MathGrit Coach Note

Let primitive roots reveal the structural theorem; then compute only what remains.

Try it on:

Practice a contest problem where the key step is using generators of modular multiplication groups to control powers and residues.