0 Daumen
405 Aufrufe

Aufgabe:

Finden Sie alle ganzen Zahlen x, sodass 29x ≡ 7 (mod 2023) gilt


Problem/Ansatz:

kann man 29^-1 irgendwie mit dem Taschenrechner ausrechnen oder kann mir jemand erklären wie man das so rechnet?

ich weiß das man beide Seiten mit 29^-1 multiplizieren muss. Jedoch weiß ich nicht wie man das Inverse Element hier ausrechnet.

Avatar von

3 Antworten

0 Daumen

Das multiplikativ Inverse lässt sich mit dem erweiterten euklidischen Algorithmus berechnen.

Siehe https://de.wikipedia.org/wiki/Erweiterter_euklidischer_Algorithmus

Kontrolllösung: \(29^{-1}=1744\).

Avatar von 18 k
0 Daumen

https://de.wikipedia.org/wiki/Erweiterter_euklidischer_Algorithmus

blob.png

Es gilt also x = -279 + k·2023 mit k ∈ ℤ.

für k = 1 ergibt sich dann auch 1744.

Avatar von 487 k 🚀
0 Daumen

Ich würde hier empfehlen, den Modul \(2023=7\cdot 17^2\) aufzuspalten und dann per Chinesischem Restsatz die Lösung zu ermitteln:

mod 7:

\(29x\equiv_7 x\equiv_7  0\: (7)\)

mod 17²=289:

Hier ist es günstig zu sehen, dass

\(29\cdot 10 = 290 = 289 +1\)

Daher gilt

\(10\cdot 29x\equiv_{289} 1\cdot x\equiv_{289} 70 \: (289)\)

Jetzt setzt du die Lösung mit dem Chinesichen Restsatz zusammen, wobei \(\left[ 7\right]_{289}^{-1}\) das Inverse von 7 mod 289 ist:

\(x = 0\cdot \ldots + 70 \cdot \left[ 7\right]_{289}^{-1}\cdot 7\)

Per Euklid (\(289=41\cdot 7+2,\: 7=3\cdot 2 + 1\)) findest du schnell

\(\left[ 7\right]_{289}^{-1} = 124\)

Damit ergibt sich die Lösung:

\(x\equiv_{2023} 70 \cdot 124 \cdot 7 \equiv_{2023} 70 \: (2023)\)

Avatar von 11 k

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community