Wenn die Moduln mal nicht teilerfremd sind . . . Johannes Cuno Wintersemester 2014/2015 Im Rahmen von Aufgabe 46 haben wir zwei Kongruenzsysteme betrachtet, bei denen die Moduln nicht paarweise teilerfremd waren. Aus diesem Grund war der Chinesische Restsatz erstmal nicht anwendbar. Wir hatten aber Gl¨ uck: Bei Aufgabe 46a konnten wir eine Kongruenz streichen und waren dann doch in einer Situation mit paarweise teilerfremden Moduln, bei Aufgabe 46b gab es einen Widerspruch. Wie man solche Kongruenzsysteme l¨osen kann, ohne sich auf sein Gl¨ uck verlassen zu m¨ ussen, m¨ochte ich Euch hier an zwei Beispielen zeigen. Methode A: Das System per Hand l¨ osen! Betrachten wir erneut das Beispiel aus Aufgabe 46a: I x ≡ 2 mod 3 II x ≡ 2 mod 9 III x ≡ 1 mod 10 Kongruenz I ist genau dann erf¨ ullt, wenn es ein k1 ∈ Z gibt, sodass x = 3k1 + 2 ist. Wir wollen uns u ucke der Form 3k1 + 2 zugleich ¨berlegen, welche Ausdr¨ L¨ osungen der anderen beiden Kongruenzen sind. 3k1 + 2 ist genau dann auch eine L¨osung von Kongruenz II, wenn es ein k2 ∈ Z gibt, sodass 3k1 + 2 = 9k2 + 2 ist. F¨ ur welche Werte von k1 ∈ Z das der Fall ist, folgt aus Aufgabe 39: 3k1 + 2 = 9k2 + 2 ⇔ 3k1 − 9k2 = 0 ⇔ (k1 , k2 ) = (0 + λ · −9/3, 0 − λ · 3/3) 1 Also sind die simultanen L¨osungen von Kongruenz I und Kongruenz II genau die Ausdr¨ ucke der Form x = 3 · (0 + λ · −9/3) + 2 = −9λ + 2, wobei λ ∈ Z. Weiters ist −9λ + 2 genau dann auch eine L¨osung von Kongruenz III, wenn es ein k3 ∈ Z gibt, sodass −9λ + 2 = 10k3 + 1 ist. F¨ ur welche Werte von λ ∈ Z das der Fall ist, folgt erneut aus Aufgabe 39: −9λ + 2 = 10k3 + 1 ⇔ 1 = 9λ + 10k3 ⇔ (λ, k3 ) = (−1 + µ · 10/1, 1 − µ · 9/1) Also sind die simultanen L¨ osungen der drei Kongruenzen genau die Ausdr¨ ucke der Form x = −9 · (−1 + µ · 10/1) + 2 = −90µ + 11, wobei µ ∈ Z. Methode B: Chinesischer Restsatz fu ¨ r Experten ¨ Zun¨ achst beweisen wir ein Lemma, das wir eigentlich schon in der Ubungsstunde h¨ atten gebrauchen k¨ onnen. Lemma 1 Sei λ ∈ N. Wenn x ≡ a mod λm gilt, dann gilt auch x ≡ a mod m. Das bedeutet: Wenn wir die Restklasse von x modulo λm kennen, dann ist damit auch die Restklasse von x modulo m eindeutig festgelegt. Beweis. Nach Voraussetzung gilt x ≡ a mod λm. Also gibt es ein k1 ∈ Z, sodass x = a + k1 λm. Nun setze k2 := k1 λ. Offenbar ist k2 ∈ Z und es gilt x = a + k2 m. Daraus folgt schließlich x ≡ a mod m. Mit diesem Lemma sieht man sofort, dass man bei Aufgabe 46a eine Kongruenz streichen kann und bei Aufgabe 46b ein Widerspruch auftaucht. Aber dieses Lemma kann noch mehr. Um einen Eindruck davon zu bekommen, wie man damit beliebige Kongruenzsysteme l¨ost, betrachten wir das folgende Beispiel: I x ≡ 5 mod 12 II x ≡ 17 mod 30 Da die Moduln 12 = 2 · 2 · 3 und 30 = 2 · 3 · 5 nicht teilerfremd sind, ist der Chinesische Restsatz erstmal nicht anwendbar. Allerdings k¨onnen wir jede der beiden Kongruenzen mit dem Chinesischen Restsatz, wie in Aufgabe 45, in Kongruenzen modulo der jeweiligen Potenzen der Primfaktoren zerlegen: 2 I x ≡ 5 mod 12 II x ≡ 17 mod 30 Ia x ≡ 1 mod 4 Ib x ≡ 2 mod 3 II a x ≡ 1 mod 2 II b x ≡ 2 mod 3 II c x ≡ 2 mod 5 Es gilt I ⇔ I a ∧ I b“ sowie II ⇔ II a ∧ II b ∧ II c“. Also gen¨ ugt es, die f¨ unf ” ” Kongruenzen auf der rechten Seite zu betrachten. Unser Lemma besagt nun, dass wir die beiden Kongruenzen II a und II b streichen k¨onnen, weil sie sich aus den Kongruenzen I a und I b ergeben. Es bleiben: Ia x ≡ 1 mod 4 Ib x ≡ 2 mod 3 II c x ≡ 2 mod 5 Und das geht wunderbar mit den Chinesischen Restsatz. Wir erhalten schließlich als L¨ osungsmenge L = {x ∈ Z | x ≡ 17 mod 60}. Fragen sind, wie immer, hochwillkommen! 3