Modulo und kleiner Fermat |
26.08.2004, 18:08 | henni | Auf diesen Beitrag antworten » | ||
Modulo und kleiner Fermat 2^49 mod 50 = ? Wenn ich es richtig verstanden habe, dann kann ich den Fermat hier nicht anwenden, da ggt(2,50) ungleich 1. (?) wie geht man den sonst an so einen Aufgabe ran, wenn man keinen T-Rechner verwenden darf? Mfg henni |
||||
26.08.2004, 20:55 | Irrlicht | Auf diesen Beitrag antworten » | ||
Hallo henni, Mehrere Wege führen nach Rom, wie es so schön heisst. Du hast ganz richtig erkannt, dass der Satz von Fermat hier nicht anwendbar ist. Da 48 = 3*16 ist, könntest du 2^49 = 2 * 2^(3*16) = 2 * (((8^2)^2)^2)^2 bestimmen und bei jedem Rechenschritt mod 50 reduzieren. Oder du verwendest den chinesischen Restsatz. Die 2 entspricht dann dem Tupel (0 mod 2, 2 mod 25). Für die zweite Komponente kannst du dann den Satz von Euler (eine Verallgemeinerung des Satzes von Fermat) anwenden. Was von den beiden Varianten nun geschickter ist, weiss ich selbst nicht, da ich es nicht ausprobiert habe. Das müsstest du dann selbst entscheiden. Liebe Grüsse, Irrlicht |
||||
28.08.2004, 13:18 | Mathe-Student | Auf diesen Beitrag antworten » | ||
andere Idee: a := 2^49 mod 50 = 2^-1 mod 50 => 4*a = 2 mod 50 => a = 38 mod 50 da 2 = 2^51 = 4 * 2^49 immer mod 0 *hofft sehr, daß das auch stimmt* |
||||
28.08.2004, 13:59 | Irrlicht | Auf diesen Beitrag antworten » | ||
Hallo Mathestudent, Leider stimmt das nicht, denn 2^51 = 48 = -2 mod 50 (Edit: Lies: ) Ausserdem existiert 2^-1 mod 50 gar nicht, weil 2 modulo 50 nicht invertierbar ist. Liebe Grüsse, Irrlicht |
||||
28.08.2004, 14:05 | kurellajunior | Auf diesen Beitrag antworten » | ||
Hallo? Also mein Taschenrechner schafft grad so noch und das ist nicht 48? Ich würde die Ansätze gerne verstehen, daher schreibt bitte nicht so stark verkürzte Dinge ins Board, das verwirrt: fragende Grüße, Jan |
||||
28.08.2004, 14:15 | Oudeis | Auf diesen Beitrag antworten » | ||
Huhu, hier ist zusätzlich zu den zwei bereits von Irrlicht angegebenen noch ein dritter Ansatz: Wir sehen sofort, daß 2^10 = 1024 ist, also 2^10 = 24 mod 50. Nun ist 24 = 25 - 1, und man kann leicht nachrechnen (binomische Formeln + vollständige Induktion), daß (25 - 1)^n (mod 50) = 25 + (-1)^n (mod 50) ist. Insbesondere folgt 2^50 (mod 50) = 24, 2^49 (mod 50) = hierkeinspoiler (weil durch zwei teilbar!), und 2^51 (mod 50) = 48 . Grüße, Oudeis |
||||
Anzeige | ||||
|
||||
28.08.2004, 14:23 | Irrlicht | Auf diesen Beitrag antworten » | ||
Entschuldige, aber es verwirrt dich wohl die Verwendung von "=" anstelle von ""? Denn dahinter schreibe ich ein "mod 50". Da das mein Vorgänger, auf den ich geantwortet habe, aber ebenfalls getan hat und es die einfachere Schreibweise ist, wenn man auf Latex verzichtet, sehe ich da kein Problem darin. Im übrigen sehe ich da kein "stark verkürztes Ding", das ich geschrieben habe. Ein wenig Mitarbeit setze ich bei meinen Posting schon voraus, vor allem wenn es dazu noch etwas ist, was man allein mit dem Taschenrechner rechnen kann, wenn man die modulo-Rechnung kennt. Der Starter kennt modulo Rechnung und ihm wird mein Ergebnis nützen - egal woher ich es hab (solange es richtig ist). Ihn verwirrt das nicht, aber ihn hätte vielleicht die Antwort vom Mathestudenten verwirrt, der einen im übrigen durchaus verständlichen Fehler machte. Liebe Grüsse, Irrlicht |
||||
28.08.2004, 15:08 | SirJective | Auf diesen Beitrag antworten » | ||
Das sehe ich auch sofort, da 48! durch 17 teilbar ist, aber 2^51 nicht |
||||
28.08.2004, 17:32 | henni | Auf diesen Beitrag antworten » | ||
Vielen Dank! Vielen Dank an euch alle. Die "kurzen" Antworten haben mir durchaus geholfen. Vielen Dank! |
||||
29.08.2004, 16:47 | Irrlicht | Auf diesen Beitrag antworten » | ||
Du hast ausversehen in einen anderen Thread gepostet, daher habe ich deine Frage von dort kopiert und zitiere es jetzt. Du rechnest gerade 2 * (((8^2)^2)^2)^2 mod 50? 8^2 (mod 50) = 64 (mod 50) = 14 14^2 (mod 50) = 196 (mod 50) = 46 46^2 (mod 50) = ... ...^2 (mod 50) = ... und 2*... (mod 50) = ... Liebe Grüsse, Irrlicht |
||||
29.08.2004, 17:24 | henni | Auf diesen Beitrag antworten » | ||
sorry, und noch mal vielen Dank. Jetzt habe ich es glaube ich begriffen. Ich komme nun auf das Ergebnis 12. Denn: ... 46^2 mod 50 = 16 16^2 mod 50 = 6 2 * 6 = 12 Ist das jetzt soweit richig? |
||||
29.08.2004, 18:29 | Irrlicht | Auf diesen Beitrag antworten » | ||
Ja, das ist es. Liebe Grüsse, Irrlicht |
||||
29.08.2004, 21:02 | Mathe-Student | Auf diesen Beitrag antworten » | ||
Sorry für die Verwirrung, :P Hab den Denkfehler gefunden. Ich bin irrtümlich davon ausgegangen, dass die Kardinalität der Menge {} ein Teiler von 50 sein müsste. Insbesondere hatte ich sie spontan für identisch zur Menge { } gehalten, was natürlich nicht stimmt, da die Elemente 0,10,20,30,40 nicht in der ersten Menge enthalten sind. Der Grundgedanke meiner Überlegung war jedoch nicht sooo falsch. Betrachtet man die Restklassen der Form 2^n (siehe 1. Menge) von 50 als symmetrische Gruppe und die Verdopplung als Permutation, stellt man fest, dass es ein 20er-Zyklus ist. Also folgt Wahrscheinlich auch nicht fehlerfrei, aber hoffentlich klarer. @Irrlicht: Ich weiß, dass modulo 50 nicht existiert, aber du weißt vielleicht, was gemeint war. Werde in Zukunft genauer auf die Formulierung achen. |
||||
29.08.2004, 22:51 | SirJective | Auf diesen Beitrag antworten » | ||
Hallo Mathe-Student, dein Gedanke, die Periodizität der Potenzen von 2 auszunutzen, ist absolut richtig. Es gibt auch einen allgemeinen Satz, der etwas über die Periode aussagt, nämlich den von Irrlicht erwähnten Satz von Euler. Der gilt aber nur, wenn die Basis teilerfremd zum Modul ist: Wenn a teilerfremd zu m ist, dann gilt mit der Euler-phi-Funktion (die die Anzahl der zu m teilerfremden Zahlen zwischen 1 und m angibt): Bin grad ein wenig verwirrt ob meiner Berechnungen: Gilt etwa für beliebige a und m die Kongruenz ? Edit: Stelle fest, dass meine Vermutung nicht gilt. Setze a = 2 und m = 4, dann ist phi(4) = 2, aber 2^3 != 2 (mod 4). Für konkretes a und m kann man natürlich die Periode bestimmen, und sobald man erkannt hat, dass 2^21 = 2^1 mod 50 ist, kann man dieses Resultat verwenden, deine Argumentation ist also jetzt richtig (außer dass die Verdopplung keine Permutation ist). Gruss, SirJective |
||||
30.08.2004, 00:58 | Irrlicht | Auf diesen Beitrag antworten » | ||
Hallo Mathe-Student, Mach dir mal keine Gedanken, wenn dir ein solcher Denkfehler unterläuft. Erstens machst du den bloss einmal im Leben und zweitens haben diesen Denkfehler manche hier schon hinter sich. Liebe Grüsse, Irrlicht |
||||
30.08.2004, 12:59 | Mathe-Student | Auf diesen Beitrag antworten » | ||
Danke. War auch nicht so ernst gemeint. @SirJective: Die Abbildng f(x)=2x ist auf dieser Restklassengruppe - es ist tatsächlich eine multiplikative Gruppe mit 26 als neutralem Element - eine bijektive Abbildung dieser Menge auf sich selbst. Somit eine Permutation. *im Lexikon unter Permutationen nachgeschaut*
|
||||
30.08.2004, 13:46 | Irrlicht | Auf diesen Beitrag antworten » | ||
Hallo Mathe-Student. Die Definition einer Permutation ist richtig, aber die Abbildung ist keine Permutation, denn sie ist nicht bijektiv. Das Element 1 liegt z.B. nicht im Bild, und f(1)=f(26)=2. 26 ist in Z/50Z kein neutrales Element, weder für die Addition noch für die Multiplikation. Bzgl. der Multiplikation ist weder Z/50Z noch (Z/50Z)\{0} eine Gruppe. Wenn du dich aber nur auf die geraden Zahlen dieses Restklassenringes beschränkst, dann erhältst du für f eine Bijektion. Die Teilmenge der geraden Elemente ist ein "Teilring-ohne-1", der aber sein eigenes multiplikativ neutrales Element hat, nämlich die 26. Es gibt jedoch Elemente, die kein multiplikativ inverses haben, nämlich genau die Elemente 0, 10, 20, 30, 40. Liebe Grüsse, Irrlicht |
||||
30.08.2004, 23:25 | Mathe-Student | Auf diesen Beitrag antworten » | ||
Ich beziehe mich auf die Menge M:={2^n mod 50, n Element N} und dies ist eine multiplikative Gruppe mit neutralem Element 26. f: M -> M f: x -> 2x ist hierbei bijektiv und die Umkehrabbildung ist: x -> 38x, da 38 = 2^-1 in diesem Fall sogar definiert, da M Gruppe, bzgl. der Multiplikation. |
||||
30.08.2004, 23:52 | SirJ | Auf diesen Beitrag antworten » | ||
Entschuldige, wir haben das übersehen. Diese Menge M ist genau die, die Irrlicht gefunden hat: Die geraden Zahlen modulo 50 ohne 0,10,20,30,40. Diese Teilmenge ist tatsächlich eine multiplikative Gruppe, und dass f darauf eine Bijektion ist, ist ebenfalls leicht zu sehen. Kennst du einen Weg, der aus diesen Erkenntnissen direkt liefert, dass sich die Sequenz 2^n mod 50 nach 20 Schritten wiederholt? Gruss, SirJ |
|
Verwandte Themen
Die Beliebtesten » |
Die Größten » |
|
Die Neuesten » |
|