| Autor |
Beitrag |
    
reini
| | Veröffentlicht am Donnerstag, den 31. Mai, 2001 - 10:24: | 
|
Hallo!
Der Beweis ist so krass, dass selbst unsere Tutorin nicht weiterwusste, ich hoffe, ihr seid da bewandter:
Ist peine Primzahl und sind ak (0<=k<=m) natürliche Zahlen, so gilt für alle n Element Z die Kongruenz
nS m k=0akpk = nS m k=0ak (mod p)
(also die Summe im Exponenten n^(alles was danach kommt!))
(b) für alle n Element Z ist n7=n (mod 42)
Tschüss,
Reini |
Zaph (Zaph)
| | Veröffentlicht am Donnerstag, den 31. Mai, 2001 - 17:16: |
|
Für eine Primzahl p und 0 < x < p gilt ja (bekanntlich?)
x^(p-1) = 1 mod p.
Damit gilt für alle (!) x
x^p = x mod p.
Also ist für alle x und k >= 0
x^(p^k) = x mod p.
Mit x = n^a folgt
n^(a*p^k) = n^a mod p.
Daraus jetzt der Rest ...
(b) Es reicht, n= 0,...,41 durchzuprobieren.
Schöne Grüße an deine Tutorin :-) |
reini
| | Veröffentlicht am Freitag, den 01. Juni, 2001 - 11:23: |
|
Hi Zaph!
Danke für deine Tips!!
Dennoch hab ich noch die ein oder andere Frage:
zu (a)
- wieso gilt x^(p-1) = 1 mod p ?
- wieso kann ich sagen, das wenn
n^(a*p^k) = n^a mod p auch das Teil
mit der Summe (s.o.) stimmt?
zu (b)
- wieso reicht das Druchprobieren bis 41?
Tschüss und danke!,
Reini |
Zaph (Zaph)
| | Veröffentlicht am Freitag, den 01. Juni, 2001 - 15:35: |
|
Hi Reini,
kennst du folgenden Sachverhalt?
Wenn
a = b mod n
und
c = d mod n
dann ist
a*c = b*d mod n
Damit wäre deine Frage zu (b) schon mal geklärt. Denn zu jedem n gibt es ein m mit 0 <= m < 42 und
n = m mod 42
Wenn die Behauptung aus (b) für m gezeigt ist, dann gilt
n^7 = m^7 = m = n mod 42.
Ebenso, warum die Behauptung für die Summe gilt. Beachte dabei
n^(r + s) = n^r * n^s
Etwas komplizierter ist, warum
x^(p-1) = 1 mod p
für jede Primzahl p und jedes x mit 0 < x < p gilt.
Das ist der so genannte "kleine Satz von Fermat".
Siehe hier |
|
