Determine a primitive root modulo 11.
By using this primitive root, solve the following congruence equations:
(a) $2x^4 \equiv 7 \pmod {11}$
(b) $3x^2 \equiv 5 \pmod {11}$
(c) $5x^5 \equiv 6 \pmod {11}$
We'll use Proposition (6.15): Let $r$ be a primitive root of $n$
$$ a \equiv b \pmod n \quad \implies \quad \text{ind}_r (a) = \text{ind}_r (b)$$
We'll also use Proposition (6.16): Let $r$ be a primitive root of $n$ and $\text{ind}_r (a)$ be the index of $a$ relative to $r$. Then we have the following results:
(a) $\text{ind}_r (ab) ≡ \text{ind}_r (a) + \text{ind}_r (b) \pmod {\phi (n)}$
(b) $\text{ind}_r (ak) ≡ k \; \text{ind}_r(a) \pmod {\phi (n)}$
(c) $\text{ind}_r (1) ≡ 0 \pmod {\phi (n)}$ and $\text{ind}_r (r) ≡ 1 \pmod {\phi (n)}$
The following calculations show that 2 is a primitive root of 11.
| n | 2^n | 2^n mod 11 |
| 2 | 4 | 4 |
| 5 | 32 | 10 |
| 10 | 1024 | 1 |
The following table shows the reduced residue system for 11, and the index for each residue. We can read, for example, the index of 8 relative to 2 is 3, modulo 11.
| ind_2(a) | a ≡ 2^(ind_2) mod 11 |
| 1 | 2 |
| 2 | 4 |
| 3 | 8 |
| 4 | 5 |
| 5 | 10 |
| 6 | 9 |
| 7 | 7 |
| 8 | 3 |
| 9 | 6 |
| 10 | 1 |
(a) Applying Proposition (6.15) to $2x^4 \equiv 7 \pmod {11}$ gives us
$$ \text{ind}_2(2x^4) = \text{ind}_2(7) $$
And then using Proposition (6.16)
$$ \begin{align} \text{ind}_2(2) + 4\;\text{ind}_2(x) & \equiv \text{ind}_2(7) \pmod{10} \\ \\ 4\;\text{ind}_2(x) & \equiv \text{ind}_2(7) - \text{ind}_2(2) \pmod{10} \end{align}$$
The table of indices above gives us $ \text{ind}_2(2) = 1$ and $ \text{ind}_2(7)=7$, and so
$$ 4 \; \text{ind}_2(x) \equiv 6 \pmod{10}$$
Since $g = \gcd(10, 4)=2$, and $g \mid 6$, this linear congruence has 2 incongruent solutions modulo 10.
By Proposition (3.10), we can divide through by 2, changing the modulo to $\frac{10}{\gcd(2,10)}$,
$$ 2 \; \text{ind}_2(x) \equiv 3 \equiv 8 \pmod{5}$$
And again, dividing through by 2,
$$ \text{ind}_2(x) \equiv 4 \pmod{5}$$
And so the two solutions are $\text{ind}_2(x) = 4$ and $\text{ind}_2(x)= 9$. The table of indices resolves these to
$$ x \equiv 5 \pmod {11} \quad \text{and} \quad x \equiv 6 \pmod {11}$$
The following calculations show the equation $2x^4 \equiv 7 \pmod {11}$ is valid for a selection of $x \equiv 5 \pmod {11}$ and $x \equiv 6 \pmod {11}$.
| x eq 5 mod 11 | 2x^4 mod 11 | x eq 6 mod 11 | 2x^4 mod 11 | |
| 5 | 7 | 6 | 7 | |
| 16 | 7 | 17 | 7 | |
| 27 | 7 | 28 | 7 | |
| 38 | 7 | 39 | 7 | |
| 49 | 7 | 50 | 7 | |
| 60 | 7 | 61 | 7 |
(b) Applying Proposition (6.15) to $3x^2 \equiv 5 \pmod {11}$ gives us
$$ \text{ind}_2(3x^2) = \text{ind}_2(5) $$
And then using Proposition (6.16)
$$ \begin{align} \text{ind}_2(3)+ 2\; \text{ind}_2(x) & \equiv \text{ind}_2(5) \pmod {10}\\ \\ 2\; \text{ind}_2(x) & \equiv 6 \pmod {10} \end{align}$$
Since $g = \gcd(10,2)=2$ and $g \mid 6$, this linear congruence has 2 incongruent solutions modulo 10.
Dividing through by 2,
$$ \text{ind}_2(x) \equiv 3 \pmod {5}$$
And so the two solutions are $\text{ind}_2(x) = 3$ and $x \equiv =8$. The table of indices resolve these to
$$ x \equiv 3 \pmod {11} \quad \text{and} \quad x \equiv 8 \pmod {11}$$
(c) Applying Proposition (6.15) to $5x^5 \equiv 6 \pmod {11}$ gives us
$$ \text{ind}_2(5x^5) = \text{ind}_2(6) $$
And then using Proposition (6.16)
$$ \begin{align} \text{ind}_2(5)+ 5\; \text{ind}_2(x) & \equiv \text{ind}_2(6) \pmod {10}\\ \\ 5\; \text{ind}_2(x) & \equiv 5 \pmod {10} \end{align}$$
Since $g = \gcd(10,5)=5$ and $g \mid 5$, this linear congruence has 5 incongruent solutions modulo 10.
Dividing through by 5,
$$ \text{ind}_2(x) \equiv 1 \pmod {2}$$
And so the five solutions are $\text{ind}_2(x) = 1, 3, 5, 7, 9$. The table of indices resolve these to
$$ x \equiv 2, 8, 10, 7, 6 \pmod {11} $$