de
Seitenbanner
Menu
A-Z
Aufgaben

Aufgaben zum kleinen Satz von Fermat

Artikel zum Nachlesen: Kleiner Satz von Fermat

Der interaktive Aufgabengenerator zum Thema Kleiner Satz von Fermat 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 den kleinsten, nicht negativen Wert \(x\), für den die folgende Kongruenz gilt:

\[7^{23} \equiv x \pmod{11}\]

Benutze – sofern möglich – den kleinen Satz von Fermat, um die zu berechnende Potenz zunächst zu vereinfachen.

Aufgabengenerator

Aufgabengenerator

Konfiguration anpassen
 – 
 – 
Eigene Aufgabe

Eigene Aufgabe verwenden

Gib die Zahlen $a$, $n$ und $m$ ein, für die mit dem kleinen Satz von Fermat der kleinste, nicht negative Wert \(x\) mit \(a^n \equiv x \pmod{m}\) bestimmt werden soll.

Aufgabe lösen

Musterlösung

Musterlösung

Die Basis \(7\) und der Modul \(11\) sind teilerfremd, weswegen nach dem kleinen Satz von Fermat die folgende Kongruenz gilt.

\[{7}^{11-1} = {7}^{10} \equiv 1 \pmod{11}\]

Da der Exponent der zu berechnenden Potenz größer oder gleich \(10\) ist, kann die Potenz mithilfe einer Zerlegung mit Rest des Exponenten sowie unter Anwendung der Potenzgesetze vereinfacht werden.

\[{7}^{23} = {7}^{2 \cdot 10 + 3} = {7}^{2 \cdot 10} \cdot {7}^{3} = {\left({7}^{10}\right)}^{2} \cdot {7}^{3} \equiv {1}^{2} \cdot {7}^{3} \equiv {7}^{3} \pmod{11}\]

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

\[\begin{align*}
\begin{alignedat}{3}
{7}^{3} &\equiv {7}^{2} \cdot {7}&& \pmod{11} \\[0.5em]
{7}^{2} &\equiv {\left({7}^{1} \right)}^2&& \pmod{11}
\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}
{7}^{2} &\equiv 49 \equiv 5 && \pmod{11} \\[0.5em]
{7}^{3} &\equiv 5 \cdot {7}\equiv 35 \equiv 2 && \pmod{11}
\end{alignedat}
\end{align*}\]

Das gesuchte Ergebnis lautet also wie folgt:

\[{7}^{3} \equiv 2\pmod{11}\]

Insgesamt ergibt sich das folgende Gesamtergebnis:

\[{7}^{23} \equiv {7}^{3} \equiv 2 \pmod{11}\]
Lösung überprüfen

Eigene Lösung überprüfen

Gib die berechnete Potenz ein.