(i) Show that 2 is a primitive root modulo 243.
(ii) Solve the quadratic congruence
$$ x^2 \equiv 82 \pmod {243} $$
[Note 243 is composite.]
(i) Since $243=3^5$ and 2 are co-prime, we can use Euler's Theorem which tells us
$$ 2^{\phi(243)} \equiv 1 \pmod {243} $$
We can calculate $\phi(243)$ as $ \phi(243) = \phi(2=3^5) = 3^{5-1}(3-1) = 162$, and so
$$ 2^{162} \equiv 1 \pmod {243} $$
This means the order of 2 modulo 243 divides 162. The factors of 162 are 1, 2, 3, 6, 9, 18, 27, 54, 81, 162.
The following calculations show the order of 2 is not 1, 2, 3, 6, 9, 18 or 27.
| n | 2^n | 2^n mod 243 |
| 1 | 2 | 2 |
| 2 | 4 | 4 |
| 3 | 8 | 8 |
| 6 | 64 | 64 |
| 9 | 512 | 26 |
| 18 | 262144 | 190 |
| 27 | 134217728 | 80 |
The larger factors 54 and 81 require an indirect calculation.
Testing factor 54,
$$ 2^{54} \equiv(2^{27})^2 \equiv 80^2 \equiv 6400 \equiv 82 \pmod {243} $$
Testing factor 81,
$$ 2^{81} \equiv (2^{27})^3 \equiv 80^3 \equiv 512000 \equiv 242 \pmod p $$
This leaves the factor $\phi(243)=162$ as the order of 2 modulo 243, and so 2 is a primitive root of 243.
(ii) Applying Propositions (6.15) and (6.16) to $x^2 \equiv 82 \pmod {243}$, and using the above calculation for factor 54, gives
$$ 2 \times \text{ind}_2(x) \equiv \text{ind}_2(82) \equiv 54 \pmod {162} $$
Since $g=\gcd(162,2)=2$ divides 54, the linear congruence has 2 incongruent solutions.
Dividing by two,
$$ \text{ind}_2(x) \equiv \text{ind}_2(82) \equiv 27 \pmod {81} $$
The two solutions are $\text{ind}_2 \equiv 27$ and $\text{ind}_2 \equiv 108$ modulo 162.
The corresponding solutions for $x$ are $x \equiv 80 \pmod {243}$ and $x \equiv 80^4 \equiv 163 \pmod {243}$.