0 Daumen
441 Aufrufe

Aufgabe:

(77^22 * 200^7080 +7080^84)mod 66


Problem/Ansatz:

Wie berechne ich das? Bitte schritt für Schritt

Avatar von

2 Antworten

+1 Daumen

Hier ist eine Möglichkeit, wie man vorgehen kann:

Dabei braucht man aber nicht unbedingt die \(\varphi\)-Funktion, sondern nur den kleinen Fermatschen Satz, der ein Spezialfall des Satzes von Euler ist, bei dem dann die \(\varphi\)-Funktion die entscheidende Rolle spielt.

Zunächst berechnest du den Ausdruck bzgl. der Primfaktoren des Moduls \(66\):

\(66=2\cdot 3\cdot 11\)

\(\mod 2\):

\(77^{22} \cdot 200^{7080} +7080^{84} \equiv_2 77^{22} \cdot 0^{7080} +0^{84} \equiv_2 0\)

\(\mod 3\):

\(77^{22} \cdot 200^{7080} +7080^{84} \equiv_3  (-1)^{22} \cdot (-1)^{7080} +0^{84} \equiv_3 1 \)

\(\mod 11\) - Hier benutzen wir den kleinen Fermat

\(77^{22} \cdot 200^{7080} +7080^{84}\)

\( \equiv_{11} 0^{22} \cdot 200^{7080} +(-4)^{8\cdot 10 + 4} \equiv_{11} 5^2 \equiv_{11} 3\)

Jetzt musst du nur noch die kleinste natürliche Zahl \(x\) bestimmen mit

\(x\equiv_2 0\)

\(x\equiv_3 1\)

\(x\equiv_{11} 3\)

Das kannst du durch Probieren der ersten 5 Vielfachen von 11 machen (es muss ja eine Zahl kleiner als 66 rauskommen), oder per Chinesischen Restklassensatz: (\([a^{-1}]_m\) ist hier das multiplikative Inverse von \(a\) bzgl. des Moduls \(m\))

\(x= 3\cdot [6^{-1}]_{11}\cdot 6 + 1\cdot [22^{-1}]_3\cdot 22 + 0\)

\(= 18\cdot 2 + 22\cdot 1 = 58\)

Avatar von 11 k
0 Daumen

Hallo

erst mal verwandeln 77=11mod 66 , 200=-2 mod 66

dann 11^2=-11, 11^3=11 alle Potenzen von 11 ergeben 11 oder -11 also such noch raus welches

-2^6=-2 usw

7089=18, 18^2=-6 dann du

lul

Avatar von 108 k 🚀

Ein anderes Problem?

Stell deine Frage

Ähnliche Fragen

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community