| Autor |
Beitrag |
    
Martin123
Unregistrierter Gast
| | Veröffentlicht am Mittwoch, den 12. Juni, 2002 - 13:19: | 
|
Hi!
Ich habe da eine Frage:
ich habe p (Primzahl) und a Element N, wobei a nicht von p geteilt wird. Sei
nun e die kleinste natürliche Zahl mit a^e==1 mod p ("==" heisst kongruent).
Wie kann ich folgendes beweisen:
a) es existiert ein solches e
b) ist a^n == 1 mod p für eine natürliche Zahl n, so ist e ein teiler von n
c) Es ist e ein Teiler von p-1
d) Ist q eine Primzahl, so dass natürliche Zahlen n und m existieren mit
(q^n) - 1 == 3^m, so ist q=2 und m=1.
Beim letzten müsste man doch wenn man gezeigt hat dass q=2 ist mit Hilfe von
b) zeigen können, dass n gerade ist, oder? Aber wie? |
epsilon
Unregistrierter Gast
| | Veröffentlicht am Mittwoch, den 12. Juni, 2002 - 15:54: |
|
Hi, alles fällt mir auf die Schnelle nicht ein, aber zumindest Teilergebnisse kann ich Dir liefern:
zu a)
betrachte alle Zahlen a^1, a^2, a^3, ... jeweils mod p; da es nur (p-1) mögliche Ergebnisse gibt, muss mindestens eins davon mehrfach vorkommen, also z.B. a^k == a^l (mod p)
dann ist a^(k-l) == 1 mod p
also existieren solche Exponenten; der kleinste davon ist das gesuchte e
zu b)
wenn n = k*e + d ist mit d<e, dann folgt auch a^d == 1 und damit d=0
zu c)
Es gilt a^(p-1) == 1 mod p; also ist (p-1) ein Vielfaches von e
zu d)
(ich nehme mal an, es soll (q^n) - 1 = 3^m heißen und nicht kongruent??)
q^n = 3^m + 1 rechte Seite ist ungerade + 1 = gerade
damit ist q ein Vielfaches von 2 und (weil prim) gilt q=2
allerdings habe keine Idee, wie es jetzt weitergehen kann!
Vielleicht kann jemand anders hier weiter helfen.
Gruß epsilon
|
|
