Aufgaben

Aufgaben zum Satz von Euler

Der interaktive Aufgabengenerator zum Thema Satz von Euler 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{15}

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

Musterlösung
Lösung überprüfen

Die Basis $7$ und der Modul $15$ sind teilerfremd, weswegen nach dem Satz von Euler die folgende Kongruenz gilt.

{7}^{\varphi(15)} \equiv 1 \pmod{15}

Zur Berechnung des Werts $\varphi(15)$ muss zunächst die Primfaktorzerlegung für die Zahl $15$ bestimmt werden.

Zur Bestimmung der Primfaktorzerlegung für die Zahl $15$ wird diese auf Teilbarkeit durch alle Primzahlen bis zur abgerundeten Wurzel $\lfloor\sqrt{15}\rfloor = 3$ getestet. Wird ein Primteiler gefunden, so wird dieser durch Division abgespalten und die Suche für den Quotienten fortgesetzt. Die in einem Schritt abgespaltenen Primfaktoren sowie der verbleibende Quotient sind jeweils farblich hervorgehoben.

\begin{align*} 15 &= {\color{YellowGreen} 3} \cdot {\color{CornflowerBlue} 5} \\[0.5em] &= 3 \cdot {\color{YellowGreen} 5}\end{align*}

Mithilfe der Primfaktorzerlegung der Zahl $N=15$ kann der Wert $\varphi(N)$ der Eulerschen $\varphi$-Funktion berechnet werden.

\begin{align*}\varphi(15) &= \varphi\bigl(3 \cdot 5\bigr) \\[0.5em] &= \varphi\bigl(3\bigr) \cdot \varphi\bigl(5\bigr) \\[0.5em] &= {\underbrace{\bigl(3 - 1\bigr)}_{2}} \cdot {\underbrace{\bigl(5 - 1\bigr)}_{4}} \\[0.5em] &= 8\end{align*}

Mithilfe des Werts der berechneten Eulerschen $\varphi$-Funktion ergibt sich somit die nachfolgende Kongruenz.

{7}^{\varphi(15)} = {7}^{8} \equiv 1 \pmod{15}

Da der Exponent der zu berechnenden Potenz größer oder gleich dem Wert der Eulerschen $\varphi$-Funktion ist, kann die Potenz mithilfe einer Zerlegung des Exponenten mit Rest sowie unter Anwendung der Potenzgesetze vereinfacht werden.

{7}^{23} = {7}^{2 \cdot 8 + 7} = {7}^{2 \cdot 8} \cdot {7}^{7} = {\left({7}^{8}\right)}^{2} \cdot {7}^{7} \equiv {1}^{2} \cdot {7}^{7} \equiv {7}^{7} \pmod{15}

Die Potenz ${7}^{7}$ kann mithilfe des Square-and-Multiply Verfahrens über die folgenden Zwischenschritte berechnet werden:

\begin{align*}\begin{alignedat}{3}{7}^{7} &\equiv {7}^{6} \cdot {7}&& \pmod{15} \\[0.5em]{7}^{6} &\equiv {\left({7}^{3} \right)}^2&& \pmod{15} \\[0.5em]{7}^{3} &\equiv {7}^{2} \cdot {7}&& \pmod{15} \\[0.5em]{7}^{2} &\equiv {\left({7}^{1} \right)}^2&& \pmod{15}\end{alignedat}\end{align*}

Ausrechnen durch Rückwärtseinsetzen ergibt:

\begin{align*}\begin{alignedat}{3}{7}^{2} &\equiv 49 \equiv 4 && \pmod{15} \\[0.5em]{7}^{3} &\equiv 4 \cdot {7}\equiv 28 \equiv 13 && \pmod{15} \\[0.5em]{7}^{6} &\equiv {13}^2\equiv 169 \equiv 4 && \pmod{15} \\[0.5em]{7}^{7} &\equiv 4 \cdot {7}\equiv 28 \equiv 13 && \pmod{15}\end{alignedat}\end{align*}

Das gesuchte Ergebnis lautet also wie folgt:

{7}^{7} \equiv 13\pmod{15}

Insgesamt ergibt sich das folgende Gesamtergebnis:

{7}^{23} \equiv {7}^{7} \equiv 13 \pmod{15}