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 ... |
|