de
Seitenbanner
Menu
A-Z
Aufgaben

Aufgaben zum modularen Potenzieren

Artikel zum Nachlesen: Modulares Potenzieren

Der interaktive Aufgabengenerator zum Thema Modulares Potenzieren erstellt dir eine unbegrenzte Anzahl an individuell anpassbaren Aufgaben und Beispielen und unterstützt dich dabei, diese zu bearbeiten und zu lösen – unter anderem durch ausführliche und verständliche Musterlösungen . Darüber hinaus ist dieselbe Unterstützung auch für eigene Aufgaben verfügbar.

Aufgabe erstellen

Beispielaufgaben

Beispielaufgaben

Aufgabe 1 von 2

Berechne mithilfe von modularem Potenzieren den kleinsten, nicht negativen Wert \(x\), für den die folgende Kongruenz gilt:

\[{5}^{25} \equiv x \pmod{13}\]
Aufgabengenerator

Aufgabengenerator

Konfiguration anpassen
 – 
 – 
Eigene Aufgabe

Eigene Aufgabe verwenden

Gib die Zahlen $a$, $n$ und $m$ ein, für die mithilfe von modularem Potenzieren die Potenz $a^n \pmod{m}$ berechnet werden soll.

Aufgabe lösen

Musterlösung

Musterlösung

Die Potenz \({5}^{25} \bmod{13}\) kann mithilfe des Square and Multiply Verfahrens über die folgenden Zwischenschritte berechnet werden:

\[\begin{align*}
\begin{alignedat}{3}
{5}^{25} &\equiv {5}^{24} \cdot {5}&& \pmod{13} \\[0.5em]
{5}^{24} &\equiv {\left({5}^{12} \right)}^2&& \pmod{13} \\[0.5em]
{5}^{12} &\equiv {\left({5}^{6} \right)}^2&& \pmod{13} \\[0.5em]
{5}^{6} &\equiv {\left({5}^{3} \right)}^2&& \pmod{13} \\[0.5em]
{5}^{3} &\equiv {5}^{2} \cdot {5}&& \pmod{13} \\[0.5em]
{5}^{2} &\equiv {\left({5}^{1} \right)}^2&& \pmod{13}
\end{alignedat}
\end{align*}\]

Durch Rückwärtseinsetzen kann die gesuchte Potenz nun schrittweise berechnet werden. Nach den Rechenregeln für das Potenzieren modulo m und das Multiplizieren modulo m werden nach jedem Zwischenschritt die Reste bestimmt und mit diesen weiter gerechnet, um die Zwischenergebnisse möglichst klein zu halten.

\[\begin{align*}
\begin{alignedat}{3}
{5}^{2} &\equiv 25 \equiv 12 && \pmod{13} \\[0.5em]
{5}^{3} &\equiv 12 \cdot {5}\equiv 60 \equiv 8 && \pmod{13} \\[0.5em]
{5}^{6} &\equiv {8}^2\equiv 64 \equiv 12 && \pmod{13} \\[0.5em]
{5}^{12} &\equiv {12}^2\equiv 144 \equiv 1 && \pmod{13} \\[0.5em]
{5}^{24} &\equiv {1}^2\equiv 1 && \pmod{13} \\[0.5em]
{5}^{25} &\equiv 1 \cdot {5}\equiv 5 && \pmod{13}
\end{alignedat}
\end{align*}\]

Das gesuchte Ergebnis lautet also wie folgt:

\[{5}^{25} \equiv 5\pmod{13}\]
Lösung überprüfen

Eigene Lösung überprüfen

Gib die berechnete Potenz ein.