Kapitel 14Olympiade25 Min.
Restklassen als Schubfächer
Schubfachprinzip und teilbare Summen · Abschnitt 53 von 64
Intuition
Mehr Zahlen als mögliche Reste
Modulo gibt es nur Restklassen – wie Schubfächer. Legst du mehr als Zahlen hinein, müssen mindestens zwei denselben Rest haben. Ihre Differenz ist dann durch teilbar.
Satz
Teilbare-Differenz-Satz
Unter beliebigen ganzen Zahlen existieren zwei, deren Differenz durch teilbar ist.
Gelöstes Beispiel
Acht Zahlen modulo 7
Acht Zahlen verteilen sich auf nur sieben Restklassen. Zwei besitzen denselben Rest; ihre Differenz ist ein Vielfaches von 7.
Typischer Fehler
Objekte und Fächer exakt zählen
Das Schubfachprinzip garantiert erst bei mehr Objekten als Fächern eine Kollision. Gleich viele Objekte können sich ohne Doppelbelegung verteilen.