Quadratische Kongruenzen entscheiden

Quadratische Reste · Abschnitt 43 von 64

Strategie

Zielrest mit der Tabelle vergleichen

Für kleine Module entscheidet eine vollständige Quadratreste-Tabelle sofort über die Existenz von Lösungen. Für zusammengesetzte Module kann zusätzlich in teilerfremde Faktoren zerlegt und mit CRT kombiniert werden.

Gelöstes Beispiel

Der Rest 2 modulo 11

Die Quadratreste modulo 11 sind $0,1,3,4,5,9$ . Da 2 fehlt, ist $x^2\equiv2\pmod{11}$ unlösbar.

Gelöstes Beispiel

Mehr als zwei Wurzeln

Modulo 15 besitzt $x^2\equiv4$ die vier Lösungen 2, 7, 8 und 13. Bei zusammengesetzten Modulen können mehr als zwei Quadratwurzeln auftreten.

Hinweis für Begleitende

Ausblick auf stärkere Theorie

Legendre-Symbol, Euler-Kriterium und quadratische Reziprozität verfeinern die Entscheidung für große Primzahlen. Dieses Buch nutzt zunächst vollständige Tabellen und elementare Sätze.