| Autor |
Beitrag |
    
Guillermo
| | Veröffentlicht am Donnerstag, den 08. November, 2001 - 16:23: | 
|
Sei p eine Primzahl, p == 3 mod 4 (== steht für Äquivalenz). Sei a eine ganze Zahl, die ein Quadrat mod p ist (d. h., die Kongruenz a == b^2 mod p hat eine Lösung). Zeigen Sie, dass a^((p+1)/4) eine Quadratwurzel von a mod p ist. |
Hans (Birdsong)
| | Veröffentlicht am Freitag, den 09. November, 2001 - 07:17: |
|
Guillermo :
Zu zeigen ist, dass a^((p+1)/4) ein Quadrat (!)
mod p ist (andernfalls waere die Aufgabe trivial).
Beweis :
a == b^2 (mod p)
==> a^((p+1)/4) == b^((p+1)/2) (mod p)
Nach Vorr. ist p = 4m+3 ==> (p+1)/2 = 2*(m+1)
==> a^((p+1)/4) == x^2 (mod p) mit x = b^(m+1)
mfg
Hans |
Zaph (Zaph)
| | Veröffentlicht am Freitag, den 09. November, 2001 - 15:32: |
|
Ne, Hans, Guillermao hat schon recht!
Sei b = a^((p+1)/4). Zeige: b^2 = a.
DEINE Aussage ist trivial!
Wenn a ein Quadrat ist, dann ist a^k für jedes k wieder ein Quadrat. |
Cooksen
| | Veröffentlicht am Freitag, den 09. November, 2001 - 20:28: |
|
Hallo Guillermo!
Zunächst lässt sich zeigen, dass für jede ganze Zahl b<>0 gilt:
b^(p-1) == 1 mod p.
Daraus folgt dann für a<>0 und a == b^2 mod p:
Es ist b<>0, und es gilt:
[a^((p+1)/4)]^2 = a^((p+1)/2) == [b^2]^((p+1)/2) mod p
[b^2]^((p+1)/2) = b^(p+1) = b^(p-1) * b^2 == 1 * b^2 mod p gemäß obiger Aussage.
Also: [a^((p+1)/4)]^2 == b^2 == a mod p
Für a = 0 ist die Aussage der Aufgabe trivial. q.e.d.
Wenn Du noch Hinweise brauchst für den Nachweis, dass b^(p-1) == 1 mod p gilt, musst Du Dich noch mal melden.
Gruß Cooksen |
|
