Aufgaben
Aufgaben zum modularen Potenzieren
Der interaktive Aufgabengenerator zum Thema Modulares Potenzieren erstellt dir eine unbegrenzte Anzahl an individuell anpassbaren Aufgaben 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 deine eigenen Aufgaben verfügbar.
Aufgabe 1 von 2
Berechne den kleinsten, nicht negativen Wert \(x\), für den die folgende Kongruenz gilt:
\[{5}^{25} \equiv x \pmod{13}\]
Die Potenz \({5}^{25}\) 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*}\]
Ausrechnen durch Rückwärtseinsetzen ergibt:
\[\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}\]
