Use this table of the primitive root 2 of 13 to answer the questions below.
| a mod 13 | Ind_2(a) |
| 1 | 12 |
| 2 | 1 |
| 3 | 4 |
| 4 | 2 |
| 5 | 9 |
| 6 | 5 |
| 7 | 11 |
| 8 | 3 |
| 9 | 8 |
| 10 | 10 |
| 11 | 7 |
| 12 | 6 |
(a) Solve the congruence $7^x \equiv 3 \pmod {13}$.
(b) Find the least non-negative remainder after $5^{100} × 7^{50} × 9^{99}$ is divided by 13.
(c) Determine the integers $1 \le a \le 12$ such that $x^a \equiv 9 \pmod {13}$ has no solutions.
(a) We use Propositions (6.15) and (6.16) on $7^x \equiv 3 \pmod {13}$ to give
$$ \begin{align} x \; \text{ind}_2 (7) & \equiv \text{ind}_2 (3) \pmod {\phi(13)} \\ \\ 11x & \equiv 4 \pmod {12} \end{align} $$
Since $g=\gcd(12,11)=1$ and $g \mid 4$, this linear congruence has 1 unique solution modulo 12.
Testing values of $x$ from 1 to 15 gives us the solution $x \equiv 8 \pmod {12}$.
(b) We need to find the least positive $x$ such that
$$ 5^{100} × 7^{50} × 9^{99} \equiv x \pmod {13} $$
We use Propositions (6.15) and (6.16) on $5^{100} × 7^{50} × 9^{99} \equiv x \pmod {13} $ to give
$$ \begin{align} 100 \; \text{ind}_2 (5) + 50 \; \text{ind}_2 (7) + 99 \; \text{ind}_2 (9)& \equiv \text{ind}_2 (x) \pmod {12} \\ \\ 100(9) + 50(11) + 99(8) & \equiv \text{ind}_2 (x) \pmod {12} \\ \\ \text{ind}_2 (x) & \equiv 10 \pmod{12} \end{align} $$
The table of indices gives us $x=10$. And so 10 is as the least positive remainder after $5^{100} × 7^{50} × 9^{99}$ is divided by 13.
(c) We use Propositions (6.15) and (6.16) on $x^a \equiv 9 \pmod {13}$ to give
$$ \begin{align} a \; \text{ind}_2 (x) & \equiv \text{ind}_2 (9) \pmod {\phi(13)} \\ \\ a \; \text{ind}_2 (x) & \equiv 8 \pmod {12} \end{align} $$
For the linear congruence not to have a solution, we require $g \not \mid 8$ where $g = \gcd(12,a)$.
The following calculations show for which $1 \le a \le 12$, the $\gcd(12,a)$ does not divide 8.
| a | gcd(12,a) | 8 mod gcd(12,a) |
| 1 | 1 | 0 |
| 2 | 2 | 0 |
| 3 | 3 | 2 |
| 4 | 4 | 0 |
| 5 | 1 | 0 |
| 6 | 6 | 2 |
| 7 | 1 | 0 |
| 8 | 4 | 0 |
| 9 | 3 | 2 |
| 10 | 2 | 0 |
| 11 | 1 | 0 |
| 12 | 12 | 4 |
So the values of $a$ which lead to $x^a \equiv 9 \pmod {13}$ having no solutions, are $a=3, 6, 9, 12$.