Modulo Gleichung mit einem x lösen

Question

Aufgabe:

… (Bestimmen Sie ggT(47, 17) mit dem erweiterten Euklidischen Algorithmus (beachten Sie bitte den
Hinweis aus Aufgabe G3).$$ \text{Finden Sie dann eine Zahl }  x \in  \mathbb{Z}  \text{  } 4 = 47x mod 17.$$

Problem/Ansatz:

Den ersten Teil habe ich gelöst(Lösung:1),jedoch beim zweiten Teil komme ich einfach nicht weiter.

Das Skript ist auch keine Hilfe.

Danke schon im voraus

Answer 1

Finden Sie dann eine Zahl x∈Z   :       4  ≡ 47*x    mod17.

47= 2*17+13 also ist  47 ≡ 13 mod 17

Dann ist das schon mal        4  ≡ 13*x    mod17

Jetzt brauchst du das Inverse von 13 mod 17 und das ist 4

denn 13*4 = 52 Ξ 1  mod 17

also gilt  4*4  ≡ 4*13*x    mod17

              16  ≡ 1*x    mod17

also x=16

Comments

Vielen Dank jetzt habe ich es endlich verstanden

---

4  ≡ 13*x    mod17 ist zwar richtig, "handlicher" ist aber 4  ≡ -4*x    mod17, was sofort auf die Möglichkeit x=-1 führt.

(47 kann ja nicht nur als 2*17+13, sondern auch als  3*17-4 dargestellt werden.)