Saturday, 1 August 2026

Exercise (7.3).15

By using the Law of Quadratic Reciprocity find the first primitive root of the prime modulo 223. By using this primitive root, find the square root of $32 \pmod {223}$.


If $r$ is a primitive root of 223 the smallest $j$ such that $r^j \equiv 1 \pmod {223}$ is $j=\phi(223)=222$.  We have

$$ r^{222} = 1 \pmod {223} $$

The factors of 222 are $1, 2, 3, 6, 37, 74, 111$, and are the only ones we need to test against candidate values for $r$.

However, recognising that 2, 3, 6 and 37 are factors of 74 and 111, we should test the larger 74 and 111 first to more efficiently determine whether a candidate value of $r$ is primitive or not. That is, if $r^{74} \equiv 1 \pmod {223}$ or $r^{111} \equiv 1 \pmod {223}$ then we don't need to test the smaller factors.


Let's try $r=2$. We want to evaluate $2^{111} \pmod {223}$. By Euler's Criterion $2^{\frac{223-1}{2}} \equiv 2^{111} \equiv 1 \pmod {223}$ if an only if $(\frac{2}{223})=1$. By Proposition (7.15) we have $ (\frac{2}{223}) = 1 $. And so $2^{111}\equiv 1 \pmod {223}$. 

This means 2 is not a primitive root of 223.


Let's try $r=3$. We want to evaluate $3^{111} \pmod {223}$. By Euler's Criterion $3^{111} \equiv 1 \pmod {223}$ if and only if $(\frac{3}{223}) =1$. By the result of Exercise (7.3).3(i) we have $(\frac{3}{223}) = -1$. And so $3^{111} \not \equiv 1 \pmod {223}$. 

Let's try $3^74$,

$$$ 3^{74} \equiv (3^2)^{37} \equiv (9^6)^6 \times 9 \equiv (32)^6 \times 9  \equiv 183 \pmod {223}  $

And so $3^{37} \not \equiv 1 \pmod {223}$.

The following table shows the calculations for smaller factors of 222.

j3^j3^j mod 223
133
299
32727
672960

Since none of these factors results in a congruence of 1 modulo 223, we conclude that 3 is indeed a primitive factor of 223.


We need to find $x$ such that 

$$ x^2 \equiv 32 \pmod {223} $$

The following table of indices may help.

na = 3^na = 3^n mod 223
133
299
32727
48181
524320
672960
72187180
8656194
91968359
1059049177
1117714785
1253144132
13159432396

We can read off that $3^{12} \equiv 32 \pmod {223}$. This means

$$ 3^{12} \equiv (\pm 3^6)^2 \equiv (\pm 60)^2  \equiv 32 \pmod {223} $$

And so the square roots of 32 are $60 \pmod {223}$ and $163 \pmod {223}$.


(Note we didn't use the fact that 3 is a primitive root of 223 to calculate the square roots more algebraically).