Lösungen der Kongruenz: 39x Ξ 42 mod 63.

Question

Ich komme bei folgender Aufgabe nicht weiter:

Die Aufgabenstellung lautet: Geben Sie jeweils alle Lösungen mod n der folgenden Kongruenzen an. Verwenden Sie dafür den erweiterten Algorithmus.

39x Ξ 42 mod 63

1. euklidischer Algorithmus ... ggT(63,39) = 3

>> lösbar mit genau 3 Lösungen

2. erweiterter euklidischer Algorithmus ...    5*63-8*39=3    >> x= -8      y=5     für c=3

3. erweitern auf c= 42 >> *14   daraus folgt: 70*63-112*39=42  >> x=112 y=70

4. Problem:  -112 Ξ 14 mod 63 - Wie komme ich hier auf die 14 ?

5. Eine Lösung ist also xΞ14 mod 63

6. Weitere Lösungen findet man mit 14+21n   >> x2Ξ35 ,  x3 Ξ56 mod 63

Vielen lieben Dank im Voraus :)

Answer 1

Ich kann dir nur zu 4. etwas sagen, und hoffe, der Rest ist klar:

4. Problem:  -112 Ξ 14 mod 63 - Wie komme ich hier auf die 14 ?

-112 + 2*63 = -112 + 126 = 14.

Daher -112 ≡ 14 modulo 63

Answer 2

Zitat:

(...)

4. Problem:  -112 Ξ 14 mod 63 - Wie komme ich hier auf die 14 ?

(...)

Zitat Ende.


Es ist
$$ -112 \equiv -112 + 2 \cdot 63 = 14 \mod 63. $$