| Autor |
Beitrag |
    
Emrepb (Emrepb)
Mitglied
Benutzername: Emrepb
Nummer des Beitrags: 43
Registriert: 10-2003
| | Veröffentlicht am Montag, den 08. November, 2004 - 18:09: | 
|
Schon wieder beweise!!Bitte um Hilfe!
Aufgabe:
i) Sei p Prim. Zeige, daß die Kongurenz x^2 Kongurrent 1 mod p nur die Lösungen -1, 1 hat.
ii) Sei N=p1*p2****pl das Produkt von l verschiedenen Primzahlen. Zeige, daß die Kongurenz x^2 Kongurrent 1 mod N genau 2^l viele Lsungen hat.
Danke im Voraus! |
Zaph (Zaph)
Senior Mitglied
Benutzername: Zaph
Nummer des Beitrags: 1741
Registriert: 07-2000
| | Veröffentlicht am Montag, den 08. November, 2004 - 22:34: |
|
Hi Emrepb,
i) Sei x² = 1 mod p. Dann ist p ein Teiler von x² - 1 = (x + 1)(x - 1). Da p eine Primmzahl ist, ist p ein Teiler von x - 1 oder von x + 1. Also ist x - 1 = 0 mod p oder x + 1 = 0 mod p. Somit x = 1 mod p oder x = -1 mod p. q.e.d.
ii) Für ein x mit x² = 1 mod p1*...pl gilt auch x² = 1 mod pi für i = 1,...,l. Nach (i) hat die letzte Gleichung für jedes i zwei Lösungen xi1 und xi2. Wähle für jedes i eine dieser beiden Lösungen aus. Diese nennen wir xij. Dafür gibt es 2^l Möglichkeiten. Nach dem CSR existiert für jede Auswahl ein x mit x = xij mod pi. Dann ist x² = 1 mod p1*...*pl. Zeige nun noch, dass alle diese x verschieden sind ... |
|
