# The Order of an Integer and Primitive Roots

Our focus in this section is the study of the polynomial congruence equation $x^d \equiv a \pmod{m}$, where $d \in \mathbb{N}$, $a \in \mathbb{Z}$ (not divisible by $m$), and $\text{gcd}(a, m)=1$.

## Order of an Element
The *order* of an element modulo $m$ is the key concept that leads to primitive roots.

:::info
**Definition (Order of $a$ modulo $m$)**
Let $a$ and $m$ be nonzero coprime integers. The *order of $a$ modulo $m$*, denoted $\operatorname{ord}_m a$, is the smallest positive integer $e$ such that: $$a^{e} \equiv 1 \pmod{m}$$
:::

:::warning
**Example.**
1. Order of $2$ modulo $7$: $$2^1 \equiv 2, \quad 2^2 \equiv 4, \quad 2^3 \equiv 8 \equiv 1 \pmod{7}$$ Thus, $\operatorname{ord}_7 2 = 3$.
2. Order of 3 modulo 7: $$3^1 \equiv 3, 3^2 \equiv 2, 3^3 \equiv 6, 3^4 \equiv 4, 3^5 \equiv 5, 3^6 \equiv 1 \pmod{7}$$ Thus, $\operatorname{ord}_7 3 = 6$.
:::

### Properties of the Order
:::danger
**Theorem** Let $a$ and $m$ be nonzero coprime integers. If $a^e \equiv 1 \pmod{m}$ for some positive integer $e$, then the order of $a$ divides $e$: $$\operatorname{ord}_m a \mid e$$
:::

:::danger
**Corollary** For coprime integers $a$ and $m$, the order of $a$ modulo $m$ divides Euler's totient function $\varphi(m)$: $$\operatorname{ord}_m a \mid \varphi(m)$$
:::

:::warning
**Example.** Find $\operatorname{ord}_9 7$. We know $\varphi(9) = 6$, so the order must be a divisor of 6, i.e., in $\{1, 2, 3, 6\}$.

* $7^1 \equiv 7 \pmod{9}$
* $7^2 \equiv 49 \equiv 4 \pmod{9}$
* $7^3 \equiv 7 \cdot 4 = 28 \equiv 1 \pmod{9}$Thus, $\operatorname{ord}_9 7 = 3$.
:::

## Primitive Roots
A primitive root is an element whose order is as large as possible.

:::info
**Definition (Primitive Root Modulo $m$)**
Let $a$ and $m$ be coprime integers. We say that $a$ is a *primitive root modulo $m$* if its order is equal to $\varphi(m)$: $$\operatorname{ord}_m a = \varphi(m)$$
:::

:::warning
**Example**
* 3 is a primitive root modulo 7 because $\operatorname{ord}_7 3 = 6$ and $\varphi(7)=6$.
* There are no primitive roots modulo 8, because $\varphi(8)=4$, but the maximum order is $\operatorname{ord}_8 3 = 2$ (since $3^2=9 \equiv 1 \pmod 8$).
:::

### Properties of Primitive Roots
:::danger
**Theorem** If $\operatorname{gcd}(a, m)=1$, then powers of $a$ are congruent modulo $m$ if and only if their exponents are congruent modulo the order of $a$:
$$
a^i \equiv a^j \pmod{m}
\quad \Longleftrightarrow \quad
i \equiv j \pmod{\operatorname{ord}_m a}
$$
:::

:::danger
**Theorem (Reduced Residue System)** If $a$ is a primitive root modulo $m$, then the set of its powers: $$\{a, a^2, a^3, \dots, a^{\varphi(m)}\}$$ forms a reduced residue system modulo $m$.
:::

:::warning
**Example** Let $a = 2$, $m = 9$.
* We found $\operatorname{ord}_9 2 = 6 = \varphi(9)$, so 2 is a primitive root.
* The RRS is $\{2, 2^2, 2^3, 2^4, 2^5, 2^6\} = \{2, 4, 8, 16, 32, 64\}$.
* Reducing modulo 9 gives: $\{2, 4, 8, 7, 5, 1\}$, which is indeed the RRS modulo 9.
:::

:::danger
**Theorem (Order of a Power)** If $\operatorname{gcd}(a,m)=1$, then for any positive integer $n$:
$$
\operatorname{ord}_m a^n=\frac{\operatorname{ord}_m a}{\gcd(n,\operatorname{ord}_m a)}.
$$
:::

:::warning
**Example** Compute $\operatorname{ord}_7 3^4$. We know $\operatorname{ord}_7 3=6.$ Thus
$$
\operatorname{ord}_7 3^4
= \frac{6}{\gcd(6,4)}
= \frac{6}{2}
= 3.
$$
:::

:::danger
**Corollary (Counting Primitive Roots)** Let $a$ be a primitive root modulo $m$. Then $a^n$ is a primitive root modulo $m$ if and only if $$\textrm{gcd}(n, \varphi(m)) = 1$$
:::

:::danger
**Theorem (Number of Primitive Roots)** If $m$ has at least one primitive root, then it has exactly $\varphi(\varphi(m))$ incongruent primitive roots modulo $m$.
:::

:::warning
**Example** Let $m = 11$. $\varphi(11)=10$.
* If we know 2 is a primitive root modulo 11, the number of primitive roots is $\varphi(\varphi(11)) = \varphi(10) = 4$.
* The exponents $n$ must satisfy $\operatorname{gcd}(n, 10)=1$. The set of exponents is $\{1, 3, 7, 9\}$.
* The four primitive roots are $$\{2,\, 2^3,\, 2^7,\, 2^9\} = \{2,\; 8,\; 7,\; 6
\} \pmod{11}$$
:::

:::danger
**Proposition (Order of a Product)** Let $a_1$ and $a_2$ be integers coprime to $m$. If the orders of $a_1$ and $a_2$ are coprime, then the order of their product is the product of their orders:
$$\operatorname{gcd}(\operatorname{ord}_m(a_1), \operatorname{ord}_m(a_2)) = 1 \ \Rightarrow \ \operatorname{ord}_m(a_1 a_2) = \operatorname{ord}_m(a_1) \cdot \operatorname{ord}_m(a_2)$$
:::

:::success
**Exercises**
1. Determine the following orders.a) $\operatorname{ord}_5 2$ b) $\operatorname{ord}_{10} 3$ c) $\operatorname{ord}_{13} 10$ d) $\operatorname{ord}_{10} 7$
2. Show that $\operatorname{ord}_3 2 = 2$, $\operatorname{ord}_5 2 = 4$, and $\operatorname{ord}_7 2 = 3$.
3. a) Show that 5 is a primitive root of 6. b) Show that 2 is a primitive root of 11.
4. How many incongruent primitive roots does 14 have? Find a set of this many incongruent primitive roots modulo 14.
5. Show that if $\overline{a}$ is an inverse of $a$ modulo $n$, then $\operatorname{ord}_n a = \operatorname{ord}_n \overline{a}$.
6. Show that if $n$ is a positive integer and $a$ and $b$ are integers relatively prime to $n$ such that $\operatorname{gcd}(\operatorname{ord}_n a,\ \operatorname{ord}_n b)=1,$ then $\operatorname{ord}_n(ab)=\operatorname{ord}_n a \cdot \operatorname{ord}_n b.$
7. Show that if $a$ is an integer relatively prime to the positive integer $m$ and $\operatorname{ord}_m a=st,$ then $\operatorname{ord}_m a^t =s.$
8. Show that if $m$ is a positive integer and $a$ is an integer relatively prime to $m$ such that $\operatorname{ord}_m a=m-1,$ then $m$ is prime.
9. Show that $\operatorname{ord}_{F_n} 2\le 2^{\,n+1},$ where $F_n = 2^{2^n} + 1$ is the $n$th Fermat number.
:::