# Primitive Roots Modulo Prime Powers

The ultimate goal in this section is to solve the congruence equation $x^d \equiv a \pmod{p^\alpha}$. The existence of a *primitive root* simplifies this problem significantly by converting the exponential congruence into a linear one.

* If an integer $g$ is a primitive root modulo $p$, then $\operatorname{ord}_p g = p - 1$.
* In this case, the set of powers $$\{g^0, g^1, g^2, \dots, g^{p-2}\}$$ forms a *reduced residue system* modulo $p$.
* To solve $x^d \equiv a \pmod{p}$, we can express both $x$ and $a$ as powers of the primitive root $g$:$$x \equiv g^i \pmod{p} \quad \text{and} \quad a \equiv g^j \pmod{p}$$
* Substituting these into the congruence yields $$(g^i)^d \equiv g^j \pmod{p} \quad \Rightarrow \quad g^{di} \equiv g^j \pmod{p}$$
* By the order properties, this exponential congruence is equivalent to the linear congruence: $$di \equiv j \pmod{p-1}$$ Solving this linear congruence for $i$ gives the solutions for $x$.

## Existence and Properties of Primitive Roots
These theorems establish the existence and count the number of primitive roots and elements of specific orders.

:::danger
**Theorem (Existence and Counting Orders Modulo $p$)**
Let $p$ be a prime and let $d$ be a divisor of $p-1$.
1. The polynomial $x^d - 1$ has exactly $d$ incongruent roots modulo $p$.
2. The number of incongruent integers of order $d$ modulo $p$ is exactly $\varphi(d)$.
3. (Existence) Since $p-1$ is a divisor of $p-1$, the number of primitive roots modulo $p$ is $\varphi(p-1)$.
:::

:::danger
**Theorem (Existence of Primitive Roots Modulo $p^\alpha$)**
Let $p$ be an odd prime number and let $\alpha \in \mathbb{N}$. Then there exists an integer $a$ such that $\operatorname{ord}_{p^{\alpha}} a=\varphi(p^{\alpha})$. That is, every odd prime power has a primitive root.
:::

**Note:** Primitive roots exist only modulo $p^{\alpha}$, $2p^{\alpha}$, $2$, and $4$.

## Solutions to $x^n \equiv a \pmod{m}$
These propositions provide the criterion and the number of solutions for exponential congruences when a primitive root exists.

:::danger
**Proposition (Solutions Modulo a Prime Power)**
Let $p$ be an odd prime number, and let $a$ be an integer such that $p \nmid a$. Let $n$ and $\alpha$ be positive integers. Let $d$ be the greatest common divisor $d = \operatorname{gcd}(n, \varphi(p^\alpha))$.

The number of solutions to the congruence equation: $$x^n \equiv a \pmod{p^\alpha}$$is given by: $$\begin{cases} 0 \ &\text{if } a^{\frac{\varphi(p^\alpha)}{d}} \not\equiv 1 \pmod{p^\alpha} \\ d \ &\text{if } a^{\frac{\varphi(p^\alpha)}{d}} \equiv 1 \pmod{p^\alpha} \end{cases}$$
:::

:::danger
**Corollary (Solutions Modulo a Prime)**
Let $p$ be an odd prime number, and let $a$ be an integer such that $p \nmid a$. Let $n$ be a positive integer and $d = \operatorname{gcd}(n,p-1)$.

The number of solutions to the congruence equation $x^n \equiv a \pmod{p}$ is given by:$$\begin{cases} 0 \ &\text{if } a^{\frac{p-1}{d}} \not\equiv 1 \pmod{p} \\ d \ &\text{if } a^{\frac{p-1}{d}} \equiv 1 \pmod{p} \end{cases}$$
:::

:::danger
**Corollary (Quadratic Residues - Euler Criterion)**
Let $p$ be an odd prime number, and let $a$ be an integer not divisible by $p$.
The number of solutions to the quadratic congruence $x^2 \equiv a \pmod{p}$ is: $$\begin{cases} 0 \ &\text{if } a^{\frac{p-1}{2}} \not\equiv 1 \pmod{p} \\ 2 \ &\text{if } a^{\frac{p-1}{2}} \equiv 1 \pmod{p} \end{cases}$$
:::

**Note:** The condition $a^{(p-1)/2} \equiv 1 \pmod{p}$ is equivalent to the *Euler Criterion*, which states that $a$ is a quadratic residue modulo $p$ if and only if $a^{(p-1)/2} \equiv 1 \pmod{p}$.

:::success
**Exercises**
1. Find the number of incongruent roots modulo 11 of the following polynomials.
a) $x^2 + 2$
b) $x^2 + 10$
c) $x^3 + x^2 + 2x + 2$
d) $x^4 + x^2 + 1$
2. Find the number of primitive roots of each of the following primes. a) 7 b) 13 c) 17 d) 19 e) 29 f) 47
3. Find a complete set of incongruent primitive roots of 13.
4. Show that if $p$ is a prime and $p \equiv 1 \pmod{4}$, then there is an integer $x$ such that $x^2 \equiv -1 \pmod{p}.$ (Hint: show that there is an integer $x$ of order 4 modulo $p$.)
5. (Lagrange's Theorem Consequences)
* a) Use Lagrange’s theorem to show that if $p$ is a prime and $f(x)$ is a polynomial of degree $n$ with integer coefficients and more than $n$ roots modulo $p$, then $p$ divides every coefficient of $f(x)$.
* b) Let $p$ be prime. Using part (a), show that every coefficient of the polynomial $$f(x) = (x-1)(x-2)\cdots(x-(p-1)) - x^{p-1} + 1$$ is divisible by $p$.
* c) Using part (b), give a proof of Wilson’s theorem. (Hint: Consider the constant term of $f(x)$.)
6. (Constructing Primitive Roots) A systematic method for constructing a primitive root modulo a prime $p$ is outlined in this problem. Let the prime factorization of $\varphi(p)$ be $p-1=q_1^{\,t_1} q_2^{\,t_2} \cdots q_r^{\,t_r}$.
* a) Show that there are integers $a_1, a_2, \dots, a_r$ such that $\operatorname{ord}_p(a_i)=q_i^{\,t_i}$ for $i=1, \dots, r$.
* b) Show that $a = a_1 a_2 \cdots a_r$ is a primitive root modulo $p$.
* c) Follow the procedure outlined in parts (a) and (b) to find a primitive root modulo 29.
:::