(i) Show that 3 is a primitive root modulo $F_3 = 2^{2^3} + 1$ ($F_3$ is a Fermat prime).
(ii) Solve the quadratic congruence $x^2 \equiv −1 \pmod {F_3}$.
[The square roots of $-1 \mod {F_3}$.]
(i) If 3 is a primitive root of prime $F_3 = 2^{2^3} + 1$, then the order of 3 modulo $F_3 = 257$ is $\phi(257) = 256$.
Euler's Theorem tells us that $3^{256} \equiv 1$, and so the order of 3 must divide 256. The factors of 256 are 1, 2, 4, 8, 16, 32, 64, 128, 256.
The following table shows the order of 3 is not 1, 2, 4, 8, 16 or 32.
| n | 3^n | 3^n mod 257 |
| 1 | 3 | 3 |
| 2 | 9 | 9 |
| 4 | 81 | 81 |
| 8 | 6561 | 136 |
| 16 | 43046721 | 249 |
| 32 | 1853020188851841 | 64 |
Larger factors are not feasible to test directly, so we do so indirectly.
Testing factor 64,
$$ 3^{64} \equiv (3^{32})^2 \equiv 64^2 \equiv 4096 \equiv 241 \pmod {257}$$
Testing factor 128,
$$ 3^{128} \equiv (3^{64})^2 \equiv 241^2 \equiv 58081 \equiv 256 \pmod {257}$$
This leaves only the factor $\phi(F_3)=256$ as the order of 3 modulo $F_3$.
And so 3 is a primitive root of $F_3=2^{2^3}+1$.
(ii) Applying Propositions (6.15) and (6.16) to $x^2 \equiv −1 \pmod {F_3}$ gives us
$$ 2 \times \text{ind}_3(x) \equiv \text{ind}_3(−1) \pmod {\phi(F_3)} $$
Using $256 \equiv -1 \pmod 257$, and $\text{ind}_3(256)=128$,
$$ 2 \times \text{ind}_3(x) \equiv 128 \pmod {256} $$
Since $g=\gcd(256,2)=2$ and $g \mid 128$, this linear congruence has $g=2$ incongruent solutions modulo 256.
Dividing by 2,
$$ \text{ind}_3(x) \equiv 64 \pmod {128} $$
We have solutions $\text{ind}_3(x)=64$ and $\text{ind}_3(x)=192$. This gives us $x \equiv 241 \pmod {257}$ and $x \equiv 241 \times 256 \equiv 16 \pmod {257}$
So the two square roots of $-1$ are 16 and 241 modulo $F_3$.