(i) Show that 3 is a primitive root modulo 223 (223 is prime).
(ii) Solve the quadratic congruence
$$ x^2 \equiv 183 \pmod {223} $$
Find solutions to the Diophantine equation
$$ x^2 = 183 + 223y $$
(iii) Solve the cubic congruence
$$ x^3 \equiv -1 \pmod {223} $$
and the Diophantine equation
$$ x^3 + 1 = 223y$$
(i) We need to show the order of 3 modulo 223 is $\phi(223)=222$.
Because 223 is prime, we can use Euler's Theorem which tells us $3^{\phi(223)} \equiv 3^{222} \equiv 1 \pmod {223}$.
The order of 3 modulo 223 will be a factor of 222. These factors are 2, 3, 6, 37, 74, 111, 222, are the only indices of 3 we need to test. The following calculations show the order is not 2, 3 or 6.
| n | 3^n | 3^n mod 223 |
| 2 | 9 | 9 |
| 3 | 27 | 27 |
| 6 | 729 | 60 |
The larger factors lead to numbers too large for a calculator so we need to calculate more indirectly.
For factor 37, we have
$$ 3^{37} \equiv (3^6)^6 \times 3 \equiv 60^6 \equiv 46656000000 \times 3 \equiv 210 \times 3 \equiv 184 \pmod {223}$$
For factor 74, we have
$$ 3^{74} \equiv (3^6)^{12} \times 3^2 \equiv 60^{12} \times 9 \equiv (60^4)^3 \times 9 \equiv 132^3 \times 9 \equiv 183 \pmod {223}$$
For factor 111, we have
$$ 3^{111} \equiv (3^6)^{18} \times 3^3 \equiv 60^{18} \times 27 \equiv (136^3)^2 \times 27 \equiv 16^2 \times 27 \equiv 222 \pmod {223}$$
This leaves only 222 as the factor, and so the order of 3 modulo 223 is $\phi(223)=222$.
This means 3 is a primitive root modulo 223.
(ii) We use Propositions (6.15) and (6.16) on $ x^2 \equiv 183 \pmod {223} $ to give
$$ 2 \; \text{ind}_3 (x) \equiv \text{ind}_3(183) \pmod {222} $$
By Proposition (3.16), this has a solution for $\text{ind}_3 (x)$ if $\gcd(222, 2)=2$ divides $\text{ind}_3(183)$. We have already seen that $3^{74} \equiv 183 \pmod {223}$, and so $\text{ind}_3(183) = 74$. We have $2 \mid 74$ which means there are solutions, in fact 2 incongruent solutions modulo 222.
Dividing through by 2 we have
$$ \text{ind}_3 (x) \equiv 37 \pmod {111} $$
This means the two incongruent solutions modulo 222 are $\text{ind}_3 (x) = 37$ and $\text{ind}_3(x) = 148$. We consider each in turn.
For $\text{ind}_3 (x) = 37$ we have
$$ x \equiv 3^{37} \equiv (3^6)^6 \times 3 \equiv 60^6 \times 210 \times 3 \equiv 184 \pmod {223} $$
For $\text{ind}_3 (x) = 148$ we have
$$ x \equiv 3^{148} \equiv (3^{37})^4 \equiv (184)^4 \equiv 39 \pmod {223} $$
So the two incongruent solutions are
$$ x \equiv 37 \pmod {223} \quad \text{ and } \quad x \equiv 184 \pmod {223}$$
To solve the Diophantine equation $ x^2 = 183 + 223y $ we know the form of $x$, and only need to determine $y$.
For $x = 39 + 223t$ for some integer $t$,
$$ y = \frac{x^2 - 183}{223} = \frac{ (39+223t)^2 - 183 }{223} $$
And for $x = 184 + 223t$ for some integer $t$,
$$ y = \frac{x^2 - 183}{223} = \frac{ (184+223t)^2 - 183 }{223} $$
So the solutions are of two forms,
$$ \biggl ( x = 39 + 223t, y = \frac{ (39+223t)^2 - 183 }{223} \biggr ) $$
$$ \biggl ( x = 184 + 223t, y = \frac{ (184+223t)^2 - 183 }{223} \biggr ) $$
Note: The author's solution only has specific solutions where $t=0$, namely $(39, 6)$ and $(184,151)$.
(iii) We use Propositions (6.15) and (6.16) on $ x^3 \equiv -1 \equiv 222 \pmod {223} $ to give
$$ 3 \; \text{ind}_3 (x) \equiv \text{ind}_3(222) \pmod {222} $$
By Proposition (3.16), this has a solution for $\text{ind}_3 (x)$ if $\gcd(222, 3)=3$ divides $\text{ind}_3(222)$. We have already seen that $3^{111} \equiv 222 \pmod {223}$, and so $\text{ind}_3(222) = 111$. We have $3 \mid 111$ which means there are solutions, in fact 3 incongruent solutions modulo 222.
Dividing through by 3 we have
$$ \text{ind}_3 (x) \equiv 37 \pmod {74} $$
This means the three incongruent solutions modulo 222 are $\text{ind}_3 (x) = 37$, $\text{ind}_3(x) = 111$ and $\text{ind}_3(x) = 185$. We consider each in turn.
For $\text{ind}_3 (x) = 37$, from above we have
$$ x \equiv 3^{37} \equiv 184 \pmod {223} $$
For $\text{ind}_3 (x) = 111$, from above we have
$$ x \equiv (3^{37})^3 \equiv (184)^3 \equiv 222 \pmod {223} $$
For $\text{ind}_3 (x) = 185$, from above we have
$$ x \equiv (3^{37})^5 \equiv (184)^5 \equiv 40 \pmod {223} $$
So the three incongruent solutions are
$$ x \equiv 40 \pmod {223} \quad \text{ and } \quad x \equiv 184 \quad \text{ and } \equiv x \equiv 222 \pmod {223}$$
To solve the Diophantine equation $ x^3 + 1 = 223y$ we know the form of $x$, and only need to determine $y$.
For $x = 40 + 223t$ for some integer $t$,
$$ y = \frac{x^3 + 1}{223} = \frac{(40+223t)^3 + 1}{223} $$
For $x = 184 + 223t$ for some integer $t$,
$$ y = \frac{x^3 + 1}{223} = \frac{(184+223t)^3 + 1}{223} $$
For $x = 222 + 223t$ for some integer $t$,
$$ y = \frac{x^3 + 1}{223} = \frac{(222+223t)^3 + 1}{223} $$
So the solutions are of three forms,
$$ \biggl ( x = 40 + 223t, y = \frac{(40+223t)^3 + 1}{223} \biggr ) $$
$$ \biggl ( x = 184 + 223t, y = \frac{(184+223t)^3 + 1}{223} \biggr ) $$
$$ \biggl ( x = 222 + 223t, y = \frac{(222+223t)^3 + 1}{223} \biggr ) $$
Note: The author's solution only has specific solutions where $t=0$, namely $(40, 287)$, $(184,27935)$ and $(222,49063)$.