Berechnung großer Potenzen (Satz von Euler)

22.10.2020, 19:41	student1978	Auf diesen Beitrag antworten »
Berechnung großer Potenzen (Satz von Euler) Meine Frage: Hallo! Wir müssen 27^41 % 77 mithilfe des Satzes von Euler berechnen. Als Hinweis haben wir folgendes Beispiel bekommen: 3^178 = 3^58 * 3^58 * 3^58 * 3^4 = 1 * 1 * 1 * 81 81 mod 59 = 22 Meine Ideen: Das Beispiel kann ich, wenn ich es richtig verstanden habe, gut nachvollziehen. Soweit ich das verstehe wurde hier phi(59) = 58 berechnet und die 3^178 dementsprechend aufgeteilt. Oder? Ich habe das dann auch bei unserer Aufgabe versucht und phi(77) = 60 berechnet, aber da 60 > 41 ist bin ich mir ziemlich sicher das diese Vorgehensweise falsch ist. Gibt es hier vielleicht eine feste Formel die man auswendig lernen und anwenden können muss?
23.10.2020, 00:07	Finn_	Auf diesen Beitrag antworten »
Mach mal zu der 27 die Primfaktorzerlegung.
23.10.2020, 10:07	HAL 9000	Auf diesen Beitrag antworten »
Manchmal kann man diesen "günstigeren" größeren Exponenten auch durch eine moduläquivalente Basisänderung erzwingen. So ein Beispiel hatte ich neulich in einem anderen Forum: $\begin{eqnarray} 2^{11} \equiv 25^{11} = \left(5^2\right)^{11} = 5^{22}\equiv 1\bmod 23 \end{eqnarray}$ gemäß Kleinem Fermat, wobei zunächst per $\begin{eqnarray} 2\equiv 25\bmod 23 \end{eqnarray}$ die Basis künstlich "vergrößert" wurde, um auf diesen günstigen Exponenten 22 zu kommen. Jetzt kann man natürlich sagen: $\begin{eqnarray} 2^{11}\bmod 23 \end{eqnarray}$ kann man ja auch noch gut direkt zu Fuß ausrechnen. Richtig, es soll ja auch nur das Prinzip verdeutlichen, welches man dann ggfs. auch bei weit größeren Modulen/Exponenten anwenden kann.
23.10.2020, 11:23	student1978	Auf diesen Beitrag antworten »
@Finn_ Das wäre dann hier wohl: Primfaktorzerlegung: 27 = 3 * 3 * 3 27^41 = 3^41 * 3^41 * 3^41 Aber ich sehe nicht wirklich wie das hier weiterhelfen kann, der Exponent ist immer noch derselbe...
23.10.2020, 11:36	student1978	Auf diesen Beitrag antworten »
@HAL 9000 Also könnte man es auch so schreiben: 27^41 % 77 = 50^41 % 77 50 lässt sich aber nicht durch eine Zahl hoch eine andere Zahl darstellen, so wie bei deinem Beispiel die 25 als 5^2. Oder doch?
23.10.2020, 12:14	HAL 9000	Auf diesen Beitrag antworten »
Nein, im vorliegenden Fall ist der obige Trick gar nicht nötig (war vlt. ein Fehler von mir, den jetzt schon zu nennen). Außerdem sind wir hier bei Modul 77 und nicht 23... Nein, es geht um $\begin{eqnarray} 27^{41} = \left(3^3\right)^{41} = 3^{3\cdot 41} = 3^{123} \end{eqnarray}$ , das hättest du erkennen sollen (müssen).
Anzeige

23.10.2020, 12:49	student1978	Auf diesen Beitrag antworten »
@HAL 9000 Ach so ja das stimmt. Das hätte ich wohl wirklich merken sollen. Aber ich bin komplett neu in dem Thema, also entschuldige bitte dass ich mich am Anfang etwas unfähig anstelle...

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »