Kongruenzsystem vereinfachen

Question

Aufgabe:

Finden Sie (falls möglich) eine ganze Zahl z so, dass die folgenden Kongruenzen erfüllt sind.

3z ≡ 4 mod 5

5z ≡ 2 mod 6

2z ≡ 3 mod 7

Problem/Ansatz:

Grundsätzlich habe ich kein Problem beim Lösen des Kongruenzsystems, jedoch weiß ich jetzt nicht, wie ich am besten die Faktoren vor z "wegbekomme".

Answer 1

3z ≡ 4 mod 5

Dazu brauchst du das Inverse von 3 mod 5. das wäre hier die 2, weil 2*3=6≡ 1 mod 5.

Also multiplizierst du auf beiden Seiten mit 2 und hast

2*3z≡ 2*4 mod 5   bzw.   1z≡ 3 mod 5  also schon mal z≡ 3 mod 5.

Beim nächsten das Inverse von 5 mod 6 ist die 5 selbst; denn 5*5≡ 1 mod 6.

Also auf beiden Seiten mal 5 und

bei der dritten ist 4 das Inverse von 2 mod 7.

Dann bekommst du

z≡ 3 mod 5  und z≡ 4 mod 6 und z≡ 5 mod 7

und die Faktoren vor dem z sind weg.

Comments

Das ist relativ simpel muss ich sagen. Das Inverse rechne ich jetzt mittels ggT (z.B. ggT(5,3)) aus. Oder gibt es dazu noch einfachere Wege um das Inverse zu bestimmen?

Answer 2

3z-4=5x  ,  3z=5x+4  ->  9, 24, 39, 54; ...  -> z = 3; 8; 13; 18; ... ; 68; ...; 108; ...; 118; ...;

5z-2=6y  ,  5z=6y+2  -> 20; 50; 80; 110; .. -> z = 4; 10; 16; 22; 28;...; 40; ...; 58; ...; 88; ...; 118; ...;

2z-3=7u  ,  2z=7u+3   -> 10; 24; 38; 52; ...-> z = 5; 12; 19; 26; ...; 40; ...; 68; ... ;108;...

Das wäre mein Ansatz.

Die 2. und 3. Reihe für z liefert

4+6m=5+7n  und  6m-1=7n

-> z=208

3z=624

5z=1040

2z=416

-> z=208

Wegen Zeitmangels ziemlich grob skizziert.

Answer 3

2z ≡ 3 mod 7   |   *4

z ≡ 5 mod 7

ist ein Weg für die letzte Gleichung.

Comments

Tut mir leid, aber ich erkenne da nicht wie genau vorgegangen wurde :)

---

Ich habe die Gleichung mit dem mod-7-Inversen von 2 multipliziert. Dies lässt sich wegen der handlichen Zahlen natürlich für alle drei Gleichungen sofort im Kopf erledigen. Mehr als ein Schritt ist dafür sicher nicht erforderlich.

---

Ok jetzt sehe ich das auch. Also im Prinzip ist z das Inverse von 2 wenn gilt 2 * z ≡ 1 mod 7, und das ist eben für 2 * 4 der Fall, also ist 2^-1 = 4 in ℤ/ℤ_5.

---

Ja, so ist es.