(a) The prime 61 has 2 as a primitive root. Find all the primitive roots of 61.
(b) Show that the quadratic Diophantine equation $x^2 = r + 61y$, where $r$ is a primitive root of 61, has no solutions.
(c) Show that the quadratic Diophantine equation $x^2 = r + py$, where $p$ is an odd prime and $r$ is a primitive root, has no solutions.
(a) We remind ourselves of Proposition (6.18)
Let $r$ be a primitive root modulo $p$ where $p$ is prime. Then $r^m \pmod p$ is also a primitive root modulo $p$, provided $\gcd (m, p-1) = 1$.
There are $\phi(60)=12$ numbers $m$ coprime to 60, and they are $m=1, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 49, 53, 59$. The following table calculates $2^m \pmod 61$ for $m$ up to 31.
| m | 2^m | 2^m mod 61 |
| 1 | 2 | 2 |
| 7 | 128 | 6 |
| 11 | 2048 | 35 |
| 13 | 8192 | 18 |
| 17 | 131072 | 44 |
| 19 | 524288 | 54 |
| 23 | 8388608 | 10 |
| 29 | 536870912 | 30 |
| 31 | 2147483648 | 59 |
For larger values of $m$ we need to calculate indirectly.
For $m=37$,
$ 2^{37} \equiv 2^{31} \times 2^6 \equiv 59 \times 64 \equiv 55 \pmod {61}$
For $m=41$,
$ 2^{41} \equiv 2^{31} \times 2^{10} \equiv 59 \times 1024 \equiv 26 \pmod {61}$
For $m=43$,
$ 2^{43} \equiv 2^{31} \times 2^{12} \equiv 59 \times 4096 \equiv 43 \pmod {61}$
For $m=47$,
$ 2^{47} \equiv 2^{43} \times 2^{4} \equiv 43 \times 16 \equiv 17 \pmod {61}$
For $m=49$,
$ 2^{49} \equiv 2^{47} \times 2^{2} \equiv 17 \times 4 \equiv 7 \pmod {61}$
For $m=53$,
$ 2^{53} \equiv 2^{49} \times 2^{4} \equiv 7 \times 16 \equiv 51 \pmod {61}$
For $m=59$,
$ 2^{59} \equiv 2^{53} \times 2^{6} \equiv 51 \times 64 \equiv 21 \pmod {61}$
And so the primitive roots of 61 are
$$ 2, 6, 7, 10, 17, 18, 26, 30, 31, 35, 43, 44, 51, 54, 55, 59 $$
(b) Solving $x^2 = r + 61y$ is equivalent to solving $x^2 = r \pmod {61}$,
Applying Propoositions (6.15) and (6.16) to $x^2 = r \pmod {61}$ we have
$$ 2\text{ind}_r \equiv 1 \pmod {60} $$
Here $g=\gcd(60,2)=2$ does not divide 1, and so the linear congruence has no solutions. This means $x^2 = r + 61y$ has no integer solutions.
(c) Solving $x^2 = r + py$ is equivalent to solving $x^2 = r \pmod {p}$,
Applying Propoositions (6.15) and (6.16) to $x^2 = r \pmod {61}$ we have
$$ 2\text{ind}_r \equiv 1 \pmod {p-1} $$
Again, $g=\gcd(p-1,2) = 2$ and does not divide 1, and so the linear congruence has no solutions. This means $x^2 = r + py$ has no integer solutions.