Modulo und kleiner Fermat

Neue Frage »

henni Auf diesen Beitrag antworten »
Modulo und kleiner Fermat
Es geht um folgende Aufgabe:
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
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
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* Augenzwinkern
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
kurellajunior Auf diesen Beitrag antworten »

Zitat:
Original von Irrlicht
Leider stimmt das nicht, denn
2^51 = 48 = -2 mod 50


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:
verwirrt

fragende Grüße, Jan
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 smile .

Grüße,
Oudeis
 
 
Irrlicht Auf diesen Beitrag antworten »

Zitat:
Original von kurellajunior
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:
verwirrt

fragende Grüße, Jan


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
SirJective Auf diesen Beitrag antworten »

Zitat:
Original von kurellajunior
verwirrt


Das sehe ich auch sofort, da 48! durch 17 teilbar ist, aber 2^51 nicht Augenzwinkern
henni Auf diesen Beitrag antworten »
Vielen Dank!
Vielen Dank an euch alle. Die "kurzen" Antworten haben mir durchaus geholfen. Vielen Dank!
Irrlicht Auf diesen Beitrag antworten »

Zitat:
Original von henni
was genau ist "bei jedem Rechneschritt mod 50 reduzieren", und wie rechnet man das dann?


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
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?
Irrlicht Auf diesen Beitrag antworten »

Ja, das ist es.

Liebe Grüsse,
Irrlicht
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. Augenzwinkern

@Irrlicht: Ich weiß, dass modulo 50 nicht existiert, aber du weißt vielleicht, was gemeint war. Werde in Zukunft genauer auf die Formulierung achen. Gott
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
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. Augenzwinkern

Liebe Grüsse,
Irrlicht
Mathe-Student Auf diesen Beitrag antworten »

Danke. War auch nicht so ernst gemeint. Augenzwinkern

@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*

Zitat:
In der Gruppentheorie versteht man unter einer n-stelligen Permutation die bijektive Abbildung einer Menge mit n Elementen auf sich selbst, ...
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
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.
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
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »