Aufgaben

Satz von Euler – Interaktiver Aufgabengenerator

Artikel zum Nachlesen: Satz von Euler

Der interaktive Aufgabengenerator zum Thema Satz von Euler erzeugt dir eine unbegrenzte Anzahl an individuell anpassbaren, prozedural generierten Übungsaufgaben. Er unterstützt dich dabei, die Aufgaben zu lösen, das Thema ausgiebig zu üben und zu verstehen. Hierzu erstellt der Generator für jede Aufgabe eine ausführliche, verständliche Schritt-für-Schritt Musterlösung und bietet dir zudem die Möglichkeit, deine eigenen Lösungen direkt zu überprüfen. Alle Lösungen und Lösungswege werden deterministisch mithilfe der zugrundeliegenden mathematischen Verfahren berechnet. Sämtliche Hilfestellungen stehen sowohl für die freien Beispiele als auch für generierte und eigene Aufgaben im vollen Umfang zur Verfügung.

Aufgabe erstellen

Beispielaufgaben

Die ausgewählten Beispiele ermöglichen es dir, einige Generator-Konfigurationen und die verfügbare Unterstützung beim Lösen der Aufgaben unverbindlich und in aller Ruhe kennenzulernen.

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.

Aufgabengenerator

Der Aufgabengenerator ermöglicht es dir, beliebig viele, an deine individuellen Bedürfnisse angepasste Aufgaben zu generieren, um dich perfekt mit dem Thema vertraut zu machen.

Melde dich an, um unbegrenzt Übungsaufgaben zu erzeugen. Jetzt anmelden!

Konfiguration anpassen

Konfiguriere den Aufgabengenerator nach deinen Wünschen – von einfachen Beispielen bis zu anspruchsvollen Herausforderungen.

Basis:

–

Modulus:

–

Hier könnte deine generierte Aufgabe stehen!

Eigene Aufgabe

Eigene Aufgabe verwenden

Löse deine eigenen Aufgaben oder lasse deiner Neugier freien Lauf – mit voller Unterstützung des Generators.

Melde dich an, um deine eigenen Aufgaben zu verwenden und zu lösen. Jetzt anmelden!

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

\[a=\]

\[n=\]

\[m=\]

Aufgabe lösen

Musterlösung

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} \bmod{15}$ kann mithilfe des Square and Multiply Verfahrens über die folgenden Zwischenschritte berechnet werden:

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

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

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}

Lösung überprüfen

Eigene Lösung überprüfen

Gib die berechnete Potenz ein.