Der chinesische Restsatz

aus ZUM-Wiki, dem Wiki für Lehr- und Lerninhalte auf ZUM.de
Wechseln zu: Navigation, Suche

Motivation

Als Motivation gelte einmal folgendes Beispiel: Ich habe x Bonbons. Wenn ich diese Bonbons an 4 Personen verteile, bleiben 2 Bonbons übrig. Wenn ich sie an 7 Personen verteile, bleiben 3 Bonbons übrig. Wie viele Bonbons habe ich?

Es gilt:

  • x\equiv 2 mod 4
  • x\equiv 3 mod 7

Wie gehe ich vor? Ich habe einen "Trick". :-) ... Ich suche zunächst die Inversen der Moduln zueinander, also

  • 7x_1\equiv1 mod 4
  • 4x_2\equiv1 mod 7

(Diese existieren, weil beide Moduln teilerfremd sind). Wir kommen (in diesem einfachen Fall mit ein bisschen überlegen) auf

  • x_1=3
  • x_2=2.

Und jetzt rechne ich... moooment... 2\cdot 7\cdot 3 + 3\cdot 4\cdot 2 = 42 + 24 = 66. Ja, genau. 66 Bonbons hab ich, ne? (oder 94... oder 122... oder 150... mmmh... oder 38... oder 10... :-)).

Verallgemeinerung auf zwei Moduln

Seien m_1 und m_2 teilerfremd. Zu lösen sei das Kongruenzsystem:

  • x\equiv a_1 mod m_1
  • x\equiv a_2 mod m_2

Man bestimmt Zahlen x_1 und x_2 folgendermaßen:

  • m_2\cdot x_1 \equiv 1 mod m_1
  • m_1\cdot x_2 \equiv 1 mod m_2

Dann ist eine Lösung x = a_1\cdot x_1\cdot m_2 + a_2\cdot x_2\cdot m_1, denn

  • x\equiv a_1\cdot x_1\cdot m_2 + a_2\cdot x_2\cdot m_1 \equiv a_1\cdot 1 \equiv a_1 mod m_1
  • x\equiv a_1\cdot x_1\cdot m_2 + a_2\cdot x_2\cdot m_1 \equiv a_2\cdot 1 \equiv a_2 mod m_2

Weitere Lösungen ergeben sich durch x+z\cdot m_1\cdot m_2 (für z\in\mathbb{Z})

So, und jetzt richtig allgemein: Der chinesische Restsatz

Die Zahlen m_1, ..., m_n seien paarweise teilerfremd. Dann besitzt das Kongruenzsystem

  • x\equiv a_1 mod m_1
  • ...
  • x\equiv a_n mod m_n

eine Lösung mod m=m_1\cdot...\cdot m_n und alle Lösungen liegen in derselben Kongruenzklasse modulo m.

Beweis: