Primzahlen und Quadrate?
Für welche Primzahlen p ≠ 2 ist die Zahl 7 eine Quadrat modulo p.
Wie gehe ich hier vor?
Ist damit gemeint, dass
7 mod p = n²
oder
7 ≡ n² (mod p)?
Das zweite. Ich muss das allgemein machen
4 Antworten
Z. B.
7 ≡ 2² (mod 3)
7 ≡ 4² (mod 3)
7 ≡ 5² (mod 3)
7 ≡ 6² (mod 29)
7 ≡ 7² (mod 7)
7 ≡ 7² (mod 3)
7 ≡ 8² (mod 3)
7 ≡ 8² (mod 19)
7 ≡ 9² (mod 37)
7 ≡ 10² (mod 3)
7 ≡ 10² (mod 31)
7 ≡ 11² (mod 3)
7 ≡ 11² (mod 19)
...
1.)
Wenn p ein Teiler von n und damit n² wäre, wäre
n² – 7 mod p = 7 mod p = D²
und es blieben für D² nur die Quadrate 1² und 2² über (3² oder größer kann nicht sein, da a mod b ≤ a sein kann). Daraus erhält man nur die Lösung p = 2 und p = 3 (wobei p = 2 ausgeschlossen wurde).
2.)
Nun gehen wir davon aus, dass p kein Teiler von n ist, es also natürliche Zahlen l und d gibt mit
n = l • p + d => n² = (l • p)² + 2 • l • p • d + d²
=> n² mod p = d² mod p
Nun sei d² mod p = B nicht weiter durch p teilbar, genauso für 7 mod p = d.
Es folgt also aus n² ≡ 7 (mod p) dann
n² – 7 = K • p
B – b = k • p
mit ganzen Zahlen K und k.
Da B und b nicht weiter durch p teilbar sein, muss |k| = 1 sein, denn wäre |k| ≥ 2 müsse
B + b ≥ |B – d| ≥ 2 p
und nach Voraussetzungen sind B, b < p also wäre das ein Widerspruch. Man kommt also auf |k| = 1 bzw. |B – b| = p.
Sucht man sich nun eine Primzahl p aus, kann man durch berechnen von 7 mod p = b die Zahl B berechnen und damit n konstruieren, falls B eine Quadratzahl (dann sind n = m • p + √B alle Lösungen). Wenn B keine Qaudratzahl ist, kann es aber auch möglich sein - weiter kann ich es aber momentan nicht zeigen.
Danke für die Übersicht. Jedoch muss ich das ja allgemein zeigen :(
Es soll (7/p) = 1, gelten, (./.) das Legendre-Symbol.
Im quadratischen Reziprozitätsgesetz
(p/q)(q/p) = (-1)^((p-1)/2 (q-1)/2))
setzt man q = 7 und (7/p) = 1, das gibt
(p/7) = (-1)^((p+1)/2)
Daraus folgt, dass entweder
(p/7) = 1, also p ein quadratischer Rest mod 7, und gleichzeitig p = 3 (mod 4), oder
(p/7) = -1, also p kein quadratischer Rest mod 7, und gleichzeitig p = 1 (mod 4)
Oder einfacher,
p = 1, 2 4 (mod 7) und p = 3 (mod 4), oder
p = 3, 5, 6 (mod 7) und p = 1 (mod 4).
Du kannst das jetzt noch modulo 28 darstellen.
Also wären alle Primzahlen p ≠ 2 mit
p ≡ 1, 2, 3, 4, 7, 8, 9, 11, 15, 16, 18, 19, 22, 23, 25, 27 (mod 28)
die Lösung?
Oder kann man das noch vereinfachen?
~ Dieses Zeichen soll im folgenden für kongruent stehen
7 ~ n^2 (mod p) |-7
0 ~ (n^2 (mod p))-7
0 ~ ((n^2-7) (mod p))
n^2-7 ist entweder eine Primzahl oder eine zusammengesetzte Zahl. Ist n^2 eine zusammengesetzte Zahl, dann kann sie immer als Produkt von mindestens zwei Primzahlen dargestellt werden.
Beispiele mit Angabe der größten Primzahl p des Ausdrucks n^2-7:
n=4, p=3
n=5, p=3
n=6, p=29
n=7, p=7
n=8, p=19
n=9, p=37
n=10, p=31
n=11, p=19
n=12, p=137
n=13, p=3
n=14, p=7
n=15, p=109
n=16, p=83
n=17, p=47
n=18, p=317
n=19, p=59
n=20, p=131
Korrektur: Ist n^2-7 eine zusammengesetzte Zahl, dann kann sie immer als Produkt von mindestens zwei Primzahlen dargestellt werden.
Also ich komm auf die Primzahl 251. Und auf das Quadrat von 42.
42² = 1764 = 251*7 + 7. Es gilt also 42² mod 251 = 7.
... Habs aber nur durch Probieren mit einem Spreadsheet gefunden ... war der erste Treffer, gibt vielleicht mehrere ...
Habe ich mir auch schon gedacht, kann es nur nicht zeigen. Wie würdest du deine Aussage denn beweisen?
Mit dem Fundamentalsatz der elementaren Zahlentheorie: Jede natürliche Zahl größer 1 kann man als Produkt von Primzahlen darstellen:
Ist n ein Element der natürlichen Zahlen und n > 2, dann ist n^2-7 immer eine natürliche Zahl. Und für diese gilt auch der Fundamentalsatz der elementaren Zahlentheorie.
Das ist falsch.
7 ≡ 9² (mod 37)