| |
| Autor |
  2^(p-1) ≡ 1 (mod p) |
|
Dark_Querulant
Ehemals Aktiv 
Dabei seit: 17.06.2002
Mitteilungen: 245
Wohnort: Flensburg
 |  Themenstart: 2003-04-18
|
Hallo!
Ich habe mich mal ein bisschen mit Fermat beschäftigt und bin dann auf die Formel: "2p-1 = 1 mod (p)" gestoßen.
Ich habe nur leider keine Ahnung, was "mod" heißen soll. Ich habe mich schon im Internet umgeguckt, doch leider konnte ich nicht in herausfinden, was es nun heißt.
Ich wäre sehr dankbar für Hilfe!
Gruß
DQ (der Wiederauferstandene)
|
 Profil
|
matroid
Senior 
Dabei seit: 12.03.2001
Mitteilungen: 14610
Wohnort: Solingen
 |  Beitrag No.1, eingetragen 2003-04-18
|
Hi (wiedererkannter) Dark,
'mod p', gesprochen 'modulo p', bezeichnet den Rest bei Division durch p.
Gruß
Matroid
|
Profil
|
Martin_Infinite
Senior
Dabei seit: 15.12.2002
Mitteilungen: 39133
Wohnort: Münster
 |  Beitrag No.2, eingetragen 2003-04-18
|
Profil
|
Anonymous
Unregistrierter Benutzer
| Beitrag No.3, eingetragen 2003-04-18
|
Hallo,
'a mod b' steht für den ganzahligen Rest der bei der gazahligen Division übrigbleibt.
a mod b=a-int(a/b) wobei int(7,9)=7
also z.B.:
8 mod 3 = 2 (blödes Beispiel)
9 mod 3 = 0
10 mod 3 = 1
Gruß
Stefan
|
|
Anonymous
Unregistrierter Benutzer
| Beitrag No.4, eingetragen 2003-04-19
|
Es ist möglich, dass es daran liegt, dass es schon so spät ist, aber ich kann beim besten Willen keine Division in der Formel "2p-1=1 mod (p)" erkennen.
Gruß
DQ
|
|
Martin_Infinite
Senior 
Dabei seit: 15.12.2002
Mitteilungen: 39133
Wohnort: Münster
| Beitrag No.5, eingetragen 2003-04-19
|
Es ist wohl schon spät 
Das heißt, dass der Rest der Division 1/p , 2p-1 ist.
|
Profil
|
pendragon302
Senior
Dabei seit: 29.06.2002
Mitteilungen: 2003
Wohnort: Garbsen/Hannover
 | Beitrag No.6, eingetragen 2003-04-19
|
öhm Martin? Sicher?
2^(p-1)=1$mod$p bedeutet einfach nur egal welche
Primzahl du für p einsetzt der
Quotient$2^(p-1)/p$ immer den Rest 1 hat.
Zahlenbeispiel:
p=5
2^(5-1)/5=2^4/5=16/5=3$rest 1
EDIT: Natürlich muss p prim sein. War doch ein bißchen spät :-D
Gruß
-----------------
Je mehr Käse, desto mehr Löcher.
Je mehr Löcher, desto weniger Käse.
Ergo: Je mehr Käse, desto weniger Käse.
Alles, was unwahrscheinlich ist, ist auch unwahrscheinlich unwahrscheinlich. (Theorem 06)
[ Nachricht wurde editiert von pendragon302 am 2003-04-19 09:30 ]
|
Profil
|
Martin_Infinite
Senior
Dabei seit: 15.12.2002
Mitteilungen: 39133
Wohnort: Münster
| Beitrag No.7, eingetragen 2003-04-19
|
Ich bin mir nun nicht mehr sicher ... 
|
Profil
|
viertel
Senior 
Dabei seit: 04.03.2003
Mitteilungen: 27787
Wohnort: Hessen
 | Beitrag No.8, eingetragen 2003-04-19
|
Is wohl doch schon spät...
A guats Nächtle...
Dietmar
|
Profil
|
Martin
Senior
Dabei seit: 28.10.2002
Mitteilungen: 806
Wohnort: Österreich
 | Beitrag No.9, eingetragen 2003-04-19
|
Hi dark!
Mittels "a == b mod c" mit a,b,c e Z wird eine Äquivalenzrelation auf den ganzen Zahlen definiert:
a == b mod m <-> m teilt a-b
zB. m = 5
7 == 2 mod 5 weil 5 7-2 = 5 teilt. Das ist gleichbedeutend damit, das 7 und 2 bei Division durch 5 (oder allgemeiner a und b bei Divison m) den gleichen Rest lassen.
12 == 0 mod 6 <-> 6 teilt 12.
Sehen wir uns an, was dieses modulo auf den ganzen Zahlen anrichtet:
Wie oben bereits erklärt sind 2 Zahlen kongruent zu einem gewissen mod m, wenn diese den gleichen Rest bei Division durch m lassen. Wir schmeißen jetzt alle ganzen Zahlen in eine Menge, die beispielsweise bei Division durch m keinen Rest lassen. Diese Menge nennen wir <0>.
In gleicher Weise machen wir das mit den Zahlen, die einen Rest von 1, 2, 3 bis m-1 lassen (ein Rest von m ist gleichbedeutend mit einem Rest von 0).
zB. m = 12:
<0> := {..., 0, 12, 24, 36, ...}
<1> := {..., 1, 13, 25, 37, ...}
<2> := {..., 2, 14, 26, 38, ...}
...
<11> := {..., 11, 23, 35, 47, ...}
Wenn wir hier jetzt mit den Zahlen in den Mengen zählen aber die Menge nennen in der die Zahlen liegen bekommen wir:
normal gezählt: 0, 1, 2, 3, ... 11, 12, 13, 14, ... 23, 24, 25, ...
modulo gezählt: <0>, <1>, <2>, <3>, ... <11>, <0>, <1>, <2>, ... <11>, <0>, <1>, ...
Man sieht das man "im Kreis zählt" (Wie bei einer Uhr!).
Dieses a == b mod m sagt also "bzgl. mod m liegen a und b in derselben Menge". Diese Menge nennt man auch "Restklasse".
Zurück zu deinem Fermat:
2^(p-1) == 1 mod p besagt also, dass bzgl. mod p 1 und 2^(p-1) in derselben Restklasse liegt oder denselben Rest bei Division durch p lassen oder das 2^(p-1) - 1 durch p teilbar ist. Hierbei soll p eine Primzahl sein.
Nehmen wir zB. p = 3:
2^2 == 1 mod 3 <-> 3 teilt 4-1
Das gilt jetzt für jedes p (außer für 2 selbst)
Von mir auch noch einen Link:
Link.
mfg
Martin
[ Nachricht wurde editiert von Martin am 2003-04-19 05:40 ]
|
Profil
|
Dark_Querulant
Ehemals Aktiv
Dabei seit: 17.06.2002
Mitteilungen: 245
Wohnort: Flensburg
| Beitrag No.10, vom Themenstarter, eingetragen 2003-04-19
|
Danke, ich habe es jetzt verstanden (war gestern wohl wirklich ein bisschen spät).
Gibt es für diese Formel auch eine Herleitung? (Wie ich Fermat kenne, hat er selbst wohl keine Herleitung veröffentlicht)
Gruß
DQ
|
Profil
|
Fabi
Senior 
Dabei seit: 03.03.2002
Mitteilungen: 4587
 | Beitrag No.11, eingetragen 2003-04-19
|
Hi!
Ich kenne nur einen Beweis für diesen Satz, der sich der Gruppentheorie bedient. Damit ist dir aber wahrscheinlich nicht geholfen, oder?
Die Formel gilt auch nicht nur für 2, sondern für jede Zahl zwischen 1 und p-1 (z.B. auch (p-1)p-1 mod p = 1)
Gruß
Fabi
[ Nachricht wurde editiert von Fabi am 2003-04-19 15:10 ]
|
Profil
|
Martin
Senior
Dabei seit: 28.10.2002
Mitteilungen: 806
Wohnort: Österreich
| Beitrag No.12, eingetragen 2003-04-19
|
Hallo dark!
In dem Link, den ich angegeben habe, findet sich auch eine Herleitung.
mfg
Martin
|
Profil
|
| Das Thema wurde von einem Senior oder Moderator abgehakt. |
|
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2023 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die
Nutzungsbedingungen,
die Distanzierung,
die Datenschutzerklärung und das Impressum.
[Seitenanfang]
|
Home / Seite ohne Frame
Wie unterstütze ich den Matheplaneten mit Geld?
