Zeige, dass aus 5 natürlichen Zahlen stets 2 Zahlen auswählbar sind, deren Differenz durch 4 teilbar ist.

Um zu zeigen, dass sich aus 5 natürlichen Zahlen stets 2 Zahlen auswählen lassen, deren Differenz durch 4 teilbar ist, können wir den Satz der Reste verwenden. Jede natürliche Zahl kann beim Teilen durch 4 einen der folgenden Reste annehmen: 0, 1, 2 oder 3. Das bedeutet, dass es insgesamt 4 verschiedene Klassen von Resten gibt. Wenn wir 5 natürliche Zahlen haben, müssen diese Zahlen, wenn wir sie in Bezug auf ihre Reste modulo 4 betrachten, mindestens zwei Zahlen haben, die denselben Rest haben. Dies folgt aus dem Pigeonhole-Prinzip (Schubfachprinzip), das besagt, dass wenn mehr Objekte (in diesem Fall die 5 Zahlen) als Fächer (in diesem Fall die 4 möglichen Reste) vorhanden sind, mindestens ein Fach mehr als ein Objekt enthalten muss. Wenn zwei Zahlen denselben Rest r (0, 1, 2 oder 3) haben, dann ist die Differenz dieser beiden Zahlen durch 4 teilbar, da: \( a \equiv r \mod 4 \) und \( b \equiv r \mod 4 \) impliziert, dass \( a - b \equiv 0 \mod 4 \). Somit haben wir gezeigt, dass aus 5 natürlichen Zahlen immer zwei ausgewählt werden können, deren Differenz durch 4 teilbar ist.