Quadratische Reste?
Moinmoin :)
Kann mir jemand das Thema Quadratische Reste erklären? Ich verstehe es nicht ganz... Hab gehört, dass man modulo verstehn sollte dazu, aber ich kann modulo nur so im sinne von 8 mod 3 = 2.
Wäre sehr erfreut über eine Erklärung :)
Schönen Tag noch!
3 Antworten
Ein ganze Zahl a ist genau dann ein quadratischer Rest modulo m, wenn
- a teilerfremd zu m ist, also ggT(a, m) = 1 ist,
und
- es eine ganze Zahl k mit k² ≡ a (mod m) gibt, also k² - a durch m teilbar ist.
============
Beispiel 1:
5 ist ein quadratischer Rest modulo 11. Denn 5 und 11 sind offensichtlich (als zwei verschiedene Primzahlen) teilerfremd zueinander und...
Man findet beispielsweise die ganze Zahl 4 mit
4² mod 11 = 16 mod 11 = 5.
Beispiel 2:
3 ist kein quadratischer Rest modulo 4. Denn...
0² mod 4 = 0 mod 4 = 0 ≠ 3
1² mod 4 = 1 mod 4 = 1 ≠ 3
2² mod 4 = 4 mod 4 = 0 ≠ 3
3² mod 4 = 9 mod 4 = 1 ≠ 3
Man findet keine Zahl k mit k² ≡ 3 (mod 4).
Wie man aufgrund der vorigen Rechnungen erkennen kann, ist k² mod 4 immer gleich 0 oder gleich 1. Dementsprechend ist a = 1 die einzigen quadratischen Reste modulo 4 (zumindest im Bereich 0 ≤ a < 4). [Die Zahl 0 ist kein quadratischer Rest, da 0 nicht teilerfremd zu 4 ist, da ggT(0, 4) = 4 ≠ 1 ist.]
============
Im Grunde also... Berechnet man a = k² mod m für alle zu m teilerfremden Zahlen k, erhält man die quadratischen Reste a modulo m (bzw. zumindest die quadratischen Reste im Bereich 0 ≤ a < m).
Beispiel 3:
Wenn man alle quadratischen Reste a modulo 15 im Bereich 0 ≤ a < 15 sucht, so kann man die zu 15 teilerfremden Zahlen k ∈ {1, 2, 4, 7, 8, 11, 13, 14} durchgehen und jeweils k² mod 15 berechnen...
1² mod 15 = 1 mod 15 = 1 --> 1 ist quadratischer Rest mod 15
2² mod 15 = 4 mod 15 = 4 --> 4 ist quadratischer Rest mod 15
4² mod 15 = 16 mod 15 = 1 --> 1 ist quadratischer Rest mod 15
7² mod 15 = 49 mod 15 = 4 --> 4 ist quadratischer Rest mod 15
8² mod 15 = 64 mod 15 = 4 --> 4 ist quadratischer Rest mod 15
11² mod 15 = 121 mod 15 = 1 --> 1 ist quadratischer Rest mod 15
13² mod 15 = 169 mod 15 = 4 --> 4 ist quadratischer Rest mod 15
14² mod 15 = 196 mod 15 = 1 --> 4 ist quadratischer Rest mod 15
Die quadratischen Reste modulo 15 (im Bereich 0 ≤ a < 15) sind also 1 und 4.
============
Wenn es um quadratische Reste modulo einer Primzahl geht, kann man das Legendre-Symbol betrachten...
https://de.wikipedia.org/wiki/Legendre-Symbol
Das Legendre-Symbol (a/p) ist genau dann gleich 1, wenn a ein quadratischer Rest modulo der ungeraden Primzahl p ist.
Für ganze Zahlen x und y ist
x mod y
der Rest bei Division von x durch y mit Rest.
Beispiel:
Bei Division 17 : 5 erhält man 3 mit Rest 2. (Quasi wie bei schriftlicher Division ganzer Zahlen in der Grundschule mit Rest.) Wegen Rest 2 ist dann
17 mod 5
gleich der Zahl 2. Also:
17 mod 5 = 2
Wenn du irgendwo eine Kongruenz mit „≡“ geschrieben siehst, kannst du dir das quasi so denken...
a ≡ b (mod m)
ist gleichbedeutend mit
(a mod m) = (b mod m)
also gleichbedeutend damit, dass bei Division von a durch m mit Rest und bei Division von b durch m mit Rest der gleiche Rest entsteht.
Beispielsweise ist
17 ≡ 42 (mod 5)
da sowohl bei Division von 17 durch 5 (ergibt 3 mit Rest 2) als auch bei Division von 42 durch 5 (ergibt 8 mit Rest 2) der gleiche Rest entsteht.
Aber wenn dich schon sowas verwirrt, solltest du erst einmal grundlegend anfangen, dich mit der Kongruenz ganzer Zahlen zu beschäftigen, bevor du dich spezieller ins Thema mit quadratischen Resten begibst.
Vielen Dank für diese ausführliche Erklärung. :)
Jetzt hab ich es verstanden.
Dieser Abschnitt:
a ≡ b (mod m)
ist gleichbedeutend mit
(a mod m) = (b mod m)
also gleichbedeutend damit, dass bei Division von a durch m mit Rest und bei Division von b durch m mit Rest der gleiche Rest entsteht.
Hat bei mir gehangen. Jetzt check ichs :) Dankeschön
Vereinfacht gesagt ist ein quadratischer Rest modulo m das, was von einem Quadrat modulo m übrigbleiben kann. Dein Beispiel 8 mod 3 = 2 ist keiner, dafür 16 mod 3 = 1.
Die Frage, ob eine Zahl a quadratischer Rest mod m ist, ist die Frage, ob es im Restklassen-Ring Z/mZ eine Lösung x für die Kongruenz x^2 = a mod m gibt. Für grosse Moduln m kann das schwierig zu entscheiden sein - hier hilft das quadratische Reziprozitätsgesetz mit den beiden Ergänzungssätzen…
Darüber bin ich in meiner Diplomprüfung in algebraischer Zahlentheorie ausführlich ausgequetscht worden - neben dem klassischen Reziprozitätsgesetz nach Gauss auch über die Verallgemeinerung nach Artin; ist aber schon über 30 Jahre her… :-)
Vielen vielen Dank für diese ausführliche Erklärung, jedoch verwirrt mich dieses xxx ist modulo yyy. jedenfalls versteh ich das nicht mit modulo und die schreibweise