Question

Bestimmen Sie alle x ∈ Z24, die die Gleichung 253  x + 21 ≡ 3 (mod 24) erfüllen.

Ich würde als erstes umstellen bzw. modulo 24 rechnen. 

13 x ≡ 6 (mod 24)

Nun bin ich mir unsicher, da ich gelesen habe, dass die Kongruenz nur eine Lösung hat, wenn

ax ≡ b(mod m) Lösungen hat, wenn ggT(a,m) Ι b .

Hier ist aber ggT(13, 24) = 1 und somit teilt 6 nicht die 1. Das würde dann ja bedeuten, dass es keine Lösung gibt.

In der Musterslösung wird nun aber die Existenz der multiplikativen Inversen von 13 in Z24 mit dem Euklidischen Algorithmus nachgewiesen und dann in die Gleichung eingesetzt.

Am Ende erhält man dann : x ≡ 13 * 6 (mod24). 

Könnte mir jemand erklären, was hier genau gemacht wird?

Answer 1

somit teilt 6 nicht die 1.

Darum geht es doch nicht, sondern   " 1 teilt 6 "

und dann:

13 x ≡ 6 (mod 24)  auf beiden Seiten mit dem Inversen von 13 multipliziert.

13^(-1) * 13 * x  ≡  13^(-1) * 6  (mod 24)

<=>               x   ≡  13^(-1) * 6  (mod 24)

Nun ist aber 13 selbst das Inverse von 13, also

                      x   ≡  13 * 6  (mod 24)