Wie bereits geschrieben wurde, kann man die Gleichung umformen zu:
Wenn nun c, b und m natürlich sind, dann ist x exakt dann ganzzahlig, wenn c² - b ein Vielfaches von m ist. Oder anders ausgedrückt:
Die Theorie, um solche modulare quadratische Gleichungen zu lösen, ist leider etwas kompliziert. Falls du dich davon nicht abschrecken lässt:
Falls m eine ungerade Primzahl ist:
Wenn m eine ungerade Primzahl ist, kann man mithilfe des eulerschen Kriteriums prüfen, ob die Gleichung überhaupt eine Lösung besitzt.
Falls es eine Lösung c gibt, dann ist auch -c eine Lösung. Im Restklassenring modulo m sind das dann die einzigen beiden Lösungen der Gleichung.
Beispiel: Die Gleichung
hat in Z_3 exakt die beiden Lösungen c = 1 und c = -1 = 2.
Einschub: Weil uns aber nicht modulare Lösungen interessieren, sondern natürliche Lösungen, sollten wir uns an dieser Stelle klar machen, dass man so eine Lösung c liften kann: Mit c ist auch c + m, c + 2m, c + 3m etc eine Lösung der Gleichung.
Preisfrage: Wenn es eine Lösung für c gibt, wie findet man sie? Tja, hier geht's leider schon los. Für gewisse Primzahlen m sind Formeln dafür bekannt. Zum Beispiel wenn
ist, dann erhält man eine Lösung mittels
(Falls es dich interessiert: Es gibt auch Formeln für den Fall m = 5 mod 8).
Im Allgemeinen ist aber keine Formel zum Ermitteln eines quadratischen Rests bekannt, selbst bei dem einfachen Fall, dass m eine Primzahl ist. Somit bleibt dir schlimmstenfalls nur "ausprobieren".
Falls m keine Primzahl ist:
Wie du dir vorstellen kannst, wird es hier nicht einfacher ;) Ich verweise mal abkürzend auf folgendes Skript, für welches obiges Wissen vorausgesetzt wird.
https://www.uvm.edu/~cvincen1/files/teaching/spring2017-math255/quadraticequation.pdf
Beachte, dass der Ausdruck
in diesem Skript nicht für den Bruch a/b steht, sondern für das Legendre-Symbol.