Lösen von Kongruenzgleichungen

Question

Aufgabe: Löse die Kongruenz 62x=38 mod 98 (=Kongruenzzeichen)

Problem/Ansatz:

ggt(62,98)=2 (-> es existieren 2 Lösungen) , 2 teilt b also ist die Gleichung lösbar

gesamte Gleichung durch ggt teilen:

31x=19 mod 49

Weiter komme ich leider nicht,

Danke für die Hilfe!

Answer 1

Bestimme mit dem erweiterten euklidischen Algorithmus

das Inverse von 31 mod 49

und rechne dann x = 31^(-1) * 19