Index of a Number with Respect to a Primitive Root Modulo n

The index of a number $ x $ with respect to a primitive root $ r $ modulo $ n $ is simply the exponent $ m $ that you need to raise the primitive root to in order to obtain that number: $$ r^m \equiv x \pmod{n} $$

In other words, the index tells us how large the exponent of a primitive root needs to be to generate a given number.

For example, modulo $ n = 14 $, one primitive root is $ r = 5 $:

$ 5^0 \equiv 1 \pmod{14} $ → So, the index of 1 is 0
$ 5^1 \equiv 5 \pmod{14} $ → The index of 5 is 1
$ 5^2 \equiv 11 \pmod{14} $ → The index of 11 is 2
$ 5^3 \equiv 13 \pmod{14} $ → The index of 13 is 3
$ 5^4 \equiv 9 \pmod{14} $ → The index of 9 is 4
$ 5^5 \equiv 3 \pmod{14} $ → The index of 3 is 5

Key Properties of Indices

The index of a number with respect to a primitive root $ r $ follows a few fundamental properties that make modular arithmetic much easier.

The index of 1 is always zero
The index of 1 is always 0 since any number raised to the power of zero is 1. \[ \text{ind}_r(1) = 0 \]
Example: If $ r = 5 $ is a primitive root modulo 14, then $ 5^0 = 1 $, so $ \text{ind}_5(1) = 0 $.
A number and its index are directly related
If $ r^h \equiv m \pmod{n} $, then $ h $ is precisely $ \text{ind}_r(m) $. This means that to find the index of a number, you just need to determine which exponent of the primitive root produces it. \[ r^{\text{ind}_r(m)} \equiv m \pmod{n} \]
Example: If $ r = 5 $ and $ 5^3 \equiv 13 \pmod{14} $, then $ \text{ind}_5(13) = 3 $.
Indices scale when raising a number to a power
If you raise a number to a power $ h $, its index gets multiplied by $ h $: \[ \text{ind}_r(m^h) = h \cdot \text{ind}_r(m) \pmod{\varphi(n)} \] where $ \varphi(n) $ is Euler’s totient function, which counts the numbers coprime to $ n $.
Example: If $ \text{ind}_5(3) = 5 $, then: \[ \text{ind}_5(3^2) = 2 \cdot 5 = 10 \pmod{6} \equiv 4 \]
The index of a product is the sum of the indices
When multiplying two numbers, their indices add up: \[ \text{ind}_r(m \cdot m') = \text{ind}_r(m) + \text{ind}_r(m') \pmod{\varphi(n)} \] where $ \varphi(n) $ is Euler’s totient function.
Example: If $ \text{ind}_5(3) = 5 $ and $ \text{ind}_5(11) = 2 $, then: \[ \text{ind}_5(3 \cdot 11) = 5 + 2 = 7 \pmod{6} \equiv 1 \]

These properties are incredibly useful for solving modular equations, as they break down otherwise complex calculations into more manageable steps.

Example

Let’s solve the modular equation:

\[ 3x^5 \equiv 11 \pmod{14} \]

We know that $ 3 $ and $ 11 $ have specific indices with respect to the primitive root $ r = 5 $ modulo 14:

$$ \text{ind}_5(3) = 5 $$

$$ \text{ind}_5(11) = 2 $$

Rewriting the equation $ 3x^5 \equiv 11 \pmod{14} $ in terms of indices:

\[ \text{ind}_5(3) + \text{ind}_5(x^5) \equiv \text{ind}_5(11) \pmod{\varphi(14)} \]

\[ 5 + \text{ind}_5(x^5) \equiv 2 \pmod{\varphi(14)} \]

Using the property $ \text{ind}_5(x^5) = 5 \cdot \text{ind}_5(x) $:

\[ 5 + 5 \cdot \text{ind}_5(x) \equiv 2 \pmod{\varphi(14)} \]

Letting $ y = \text{ind}_5(x) $, we rewrite it as:

\[ 5 + 5y \equiv 2 \pmod{\varphi(14)} \]

Since $ \varphi(14) = 6 $, we have:

\[ 5 + 5y \equiv 2 \pmod{6} \]

Subtracting 5 from both sides:

\[ 5y \equiv -3 \equiv 3 \pmod{6}. \]

We now solve for $ y $ by checking values:

$ y = 0 \Rightarrow 5(0) = 0 \not\equiv 3 \pmod{6} $
$ y = 1 \Rightarrow 5(1) = 5 \not\equiv 3 \pmod{6} $
$ y = 2 \Rightarrow 5(2) = 10 \equiv 4 \pmod{6} $
$ y = 3 \Rightarrow 5(3) = 15 \equiv 3 \pmod{6} $ ✅

Thus, $ y \equiv 3 \pmod{6} $.

$$ y = \text{ind}_5(x) = 3 $$

This tells us that $ x $ is the number whose index is $ 3 $ with respect to $ r=5 $, meaning:

$$ x = 5^3 \equiv 13 \pmod{14} $$

So, the solution to the equation is $ x \equiv 13 \pmod{14} $.

And that’s it!