Aufgaben

Aufgaben zum kleinen Satz von Fermat

Der interaktive Aufgabengenerator zum Thema Kleiner Satz von Fermat 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:

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

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

Musterlösung
Lösung überprüfen

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}$ 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*}

Ausrechnen durch Rückwärtseinsetzen ergibt:

\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}