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

Question

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.

Answer 1

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$.

Answer 2

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

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

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

Answer 3

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)$