Eine quadratische diophantische Gleichung

Die Gleichung \[ a^2 \equiv 3 \pmod{109} \] sieht harmloser aus, als sie ist.

Man finde ein $a\in\{0,\ldots,108\}$, das sie erfüllt.

Wir lassen den Zusatz $\pmod{109}$ im Folgenden weg.
Dem auf der Matheplanet-Seite zu findenden Hinweis $121=109+12$ entnehmen wir die Gleichung \[ 11^2 \equiv 2^2\cdot 3\quad. \] Das sieht einigermaßen vielversprechend aus: auf der rechten Seite stört noch der Faktor $2^2$. Es ist $109$ eine Primzahl; also ist $(\Z / 109\Z,\ \cdot)$ eine Gruppe und damit jedes $x\in\{1,\ldots,108\}$ multiplikativ invertierbar. Wir bekommen ihn weg, indem wir beide Seiten der Gleichung mit dem multiplikativen Inversen von $2$ (ja, genau, von $2$, nicht von $4=2^2$) multiplizieren, denn es gilt $(2^2)^{-1} = (2^{-1})^2$. Also können wir wie folgt fortfahren: \[ \begin{array}{rrcl} & 11^2 &\equiv& 2^2\cdot 3\\ \iff& 11^2\cdot\left(2^2\right)^{-1} &\equiv& 3\\ \iff& 11^2\cdot\left(2^{-1}\right)^2 &\equiv& 3\\ \iff& \left(11\cdot2^{-1}\right)^2 &\equiv& 3\\ \iff& \left(11\cdot55\right)^2 &\equiv& 3\\ \iff& 605^2 &\equiv& 3\\ \iff& \left(5\cdot109+60\right)^2 &\equiv& 3\\ \iff& 60^2 &\equiv& 3\\ \end{array} \] Also ist $a=60$ eine Lösung.

Stimmt's denn auch? Ja:
\[ 60^2 \equiv 3600 \equiv 33\cdot 109+3 \equiv 3 \pmod{109}\quad. \] Damit ist eine Lösung gefunden; aber es gibt natürlich noch eine weitere. (Denn $\left(\Z / 109\Z,\ +,\ \cdot\right)$ ist ein Körper, und jede quadratische Gleichung hat über einem Körper genau zwei Lösungen.) Wolfram Alpha behauptet, dass $a=49$ eine weitere Lösung ist. Aber wie kommt man ohne Ausprobieren darauf?
Es wäre wohl machbar, wenn man einen Hinweis ähnlich wie oben gegeben hätte... Oder man lässt die Theorie der Pellschen Gleichungen (Skript S. 89) darauf los.

Wie bekommt man einen Hinweis ähnlich dem oben gegebenen? Durch Ausprobieren :)

#!/bin/bash

for ((q=0; q < 500; q++)); do

    for ((r=0; r < 500; r++)); do

        t=$((q*q-3*r*r))

        ((t == 109)) && printf "q = %d, r = %d\n" "$q" "$r"

    done

done

Die Ausgabe dieses Codes lautet

q = 11, r = 2
q = 16, r = 7
q = 28, r = 15
q = 53, r = 30
q = 101, r = 58
q = 196, r = 113
q = 376, r = 217

Die Werte q = 11, r = 2 entsprechen dem gegebenen Hinweis.
Also versuchen wir die Werte q = 16, r = 7. Indem wir mit ihnen die gleiche Rechnung durchführen wie oben, erhalten wir \[ \begin{array}{rrcl} & 16^2 &\equiv& 7^2\cdot 3\\ \iff& 16^2\cdot\left(7^2\right)^{-1} &\equiv& 3\\ \iff& 16^2\cdot\left(7^{-1}\right)^2 &\equiv& 3\\ \iff& \left(16\cdot7^{-1}\right)^2 &\equiv& 3\\ \iff& \left(16\cdot78\right)^2 &\equiv& 3\\ \iff& 1248^2 &\equiv& 3\\ \iff& \left(11\cdot109+49\right)^2 &\equiv& 3\\ \iff& 49^2 &\equiv& 3\\ \end{array} \] Also ist $a=49$ tatsächlich eine Lösung. Stimmt's denn auch? Ja:
\[ 49^2 \equiv 2401 \equiv 22\cdot 109+3 \equiv 3 \pmod{109}\quad. \] Die analoge Rechnung mit weiteren Werten für q und r durchzuführen, sei dem Leser als Übung überlassen.