2^r = 1 (mod 37) - Für welche r gilt diese Aussage? |
03.06.2010, 16:07 | PeterH | Auf diesen Beitrag antworten » | ||
2^r = 1 (mod 37) - Für welche r gilt diese Aussage? Hallo alle miteinander, Ich habe die Frage, für welche Werte für r folgendes gilt: Gibt es irgendeinen allgemeinen Ansatz, mit dem man Probleme der Form lösen kann? Ich würde mich sehr über eine Antwort freuen. Mfg PeterH Meine Ideen: |
||||
03.06.2010, 16:11 | lgrizu | Auf diesen Beitrag antworten » | ||
RE: 2^r = 1 (mod 37) - Für welche r gilt diese Aussage? da 37 ne primzahl ist kann man hier den kleinen fermat gebrauchen: a^p=a mod p also a^(p-1)=1 mod p. dein a ist die zwei, dein p ist die 37 |
||||
03.06.2010, 16:31 | PeterH | Auf diesen Beitrag antworten » | ||
RE: 2^r = 1 (mod 37) - Für welche r gilt diese Aussage? Vielen Dank für die Antwort! Für das Beispiel funktioniert es wunderbar. Doch ich habe mal eine Frage: Wenn ich a=2 und p=7 habe, ist die Potenz r nach Fermat sechs, wobei doch schon drei als Ergebnis mod 7 eins ergibt. Heißt das, dass Fermat einem zwar immer ein passendes Ergebnis gibt, dass dies jedoch nicht das kleinste sein muss? Wenn ja: Gibt es eine Möglichkeit das kleinste herauszufinden? |
||||
03.06.2010, 17:22 | lgrizu | Auf diesen Beitrag antworten » | ||
RE: 2^r = 1 (mod 37) - Für welche r gilt diese Aussage? es muss nicht das kleinste sein, aber es passt immer.... es ist nach euler eine folgerung von fermat (folgt direkt aus der 3. binomischen formel und dem kleinen fermat): kannst auch mal bei wiki gucken, ich denke, da steht noch was zu fermat, dann muss ich das nicht alles hinschreiben..... |
||||
03.06.2010, 17:27 | AD | Auf diesen Beitrag antworten » | ||
Die gesuchte Ordnung von ist auf alle Fälle ein Teiler von , das reduziert zumindest etwas die in Frage kommenden Kandidaten. Für beliebige (also nicht nur Primzahlen) und dazu teilerfremde lautet die Antwort natürlich . EDIT: Und bevor Mystic sich wieder beschwert: Es gilt sogar , wobei die Carmichael-Funktion darstellt. |
||||
03.06.2010, 17:58 | Mystic | Auf diesen Beitrag antworten » | ||
Ja, tatsächlich ist das einzige "echte" Problem die Bestimmung der Primfaktoren von r= p-1, zumindestens falls p "groß" ist, der Rest ist dann "plain sailing"...Man muss einfach dann für jeden Primfaktor q von r prüfen, ob gilt und zutreffendenfalls die Ersetzung vornehmen... Wenn eine "Verkleinerung" von r auf diesem Wege nicht mehr möglich ist, dann ist das aktuelle r die Ordnung von a mod p... Edit: Ja Arthur, freut mich zu sehen, dass mein Lamentieren über die "suboptimale" Verwendung von statt doch langsam Früchte hier trägt... |
||||
Anzeige | ||||
|
||||
03.06.2010, 20:12 | PeterH | Auf diesen Beitrag antworten » | ||
Danke sehr! |
|
Verwandte Themen
Die Beliebtesten » |
Die Größten » |
|
Die Neuesten » |