Quadratische Reste: x^2 === (p-x)^2 mod p
-
Hallo,
ich habe ein Problem - konkret geht es um die Übungsaufgabe 2
hier. Ich habe keine Ahnung, wie ich die Aussage beweisen kann.Kann mir jemand einen Denkanstoß geben?
-
n^2 = m^2 (mod p) <=> p | (n-m)(n+p), und -p < n-m < p, 0 < n+m < 2p
-
sorry, aber das verstehe ich nicht
was bedeuetet "p | (n-m)(n+p)" - und wie kommst Du darauf?
-
quadratischerrest schrieb:
sorry, aber das verstehe ich nicht
was bedeuetet "p | (n-m)(n+p)" - und wie kommst Du darauf?
Für das Warum habe ich jetzt gerade keine Antwort. Dafür hatte ich ein Bier zu viel mit meinem Nachbarn
Aber die Notation p | (n-m)(n+p) bedeutet p teilt (n-m)(n+p)
-
nochmal ausführlcher: n^2 = m^2 (mod p) => p | (n^2 - m^2) = (n - m)(m + n) => (da p prim) p | (n-m) oder p | (n+m).
Wenn jetzt n ≠ m ist, so folgt aus 0 <= n < m < p, dass -p < n-m < p, 0 < n+m < 2p.
Jetzt Fallunterscheidung: 1. Fall (p | (n-m)), dann folgt aus -p < n-m < p, dass n-m = 0, also n = m, Widerspruch zu n ≠ m.
2. Fall (p | (n+m)), dann folgt aus 0 < n+m < 2p, dass n+m = p, also n = p-m.
qed.
-
kleiner Tipp schrieb:
nochmal ausführlcher: n^2 = m^2 (mod p) => p | (n^2 - m^2) = (n - m)(m + n) => (da p prim) p | (n-m) oder p | (n+m).
Wenn jetzt n ≠ m ist, so folgt aus 0 <= n < m < p, dass -p < n-m < p, 0 < n+m < 2p.
Jetzt Fallunterscheidung: 1. Fall (p | (n-m)), dann folgt aus -p < n-m < p, dass n-m = 0, also n = m, Widerspruch zu n ≠ m.
2. Fall (p | (n+m)), dann folgt aus 0 < n+m < 2p, dass n+m = p, also n = p-m.
qed.
Danke :xmas:
-
großesdanke schrieb:
kleiner Tipp schrieb:
nochmal ausführlcher: n^2 = m^2 (mod p) => p | (n^2 - m^2) = (n - m)(m + n) => (da p prim) p | (n-m) oder p | (n+m).
Wenn jetzt n ≠ m ist, so folgt aus 0 <= n < m < p, dass -p < n-m < p, 0 < n+m < 2p.
Jetzt Fallunterscheidung: 1. Fall (p | (n-m)), dann folgt aus -p < n-m < p, dass n-m = 0, also n = m, Widerspruch zu n ≠ m.
2. Fall (p | (n+m)), dann folgt aus 0 < n+m < 2p, dass n+m = p, also n = p-m.
qed.
Danke :xmas:
Keine Ursache, gerne wieder!
:xmas1: