Chinesischer Restsatz

Einleitung

Nils hat Kekse gekauft. Wenn er sie in seiner Mathegruppe verteilt, die aus 5 Leuten besteht, bleiben 3 Kekse übrig. Hätte die Mathegruppe 7 Mitglieder, würden 2 Kekse übrig bleiben. Verteilte er seine Kekse an seine 3 besten Freunde, hätte er ebenfalls noch 2 Kekse. Jeder bekommt immer genauso viele Kekse wie alle anderen. Er will nur ganze Kekse verteilen. Wie viele Kekse hat Nils?

Diese Frage stellt er auch seiner Mathegruppe, die daraufhin das folgende Gleichungssystem aufstellt:

Dabei ist x die Anzahl der Kekse und n von i eine natürliche Zahl. Das Zeichen ≡ bedeutet, dass die rechte Seite bei der Modulooperation sich genauso verhält wie die linke Seite. Eine Zahl modulo eine andere Zahl ergibt den Rest, der bei einer Division mit der anderen Zahl übrig bleibt.

Der Mathegruppe fällt folgendes auf:

- Es gibt unendlich viele Lösungen.

- Mindestens eine Lösung liegt im Bereich von 0 bis 5*7*3=105. 105 ist das kleinste gemeinsame Vielfache von 5, 7 und 3.

Grün markierte Reste erfüllen die Gleichungen von oben. Da bei 23 alle Gleichungen erfüllt sind, ist 23 eine Lösung für die Anzahl der Kekse. Durch geschicktes Weiterprobieren kam die Mathegruppe darauf, dass es noch weitere Lösungen gibt, z. B. 128.

Applet zur Lösung