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?