Zeige, dass aus 5 natürlichen Zahlen stets zwei ausgewählt werden können, deren Differenz durch 4 teilbar ist.

Um zu zeigen, dass sich aus 5 natürlichen Zahlen stets zwei Zahlen auswählen lassen, deren Differenz durch 4 teilbar ist, können wir den Satz der Schubfachprinzip (Pigeonhole Principle) verwenden. 1. **Restklassen modulo 4**: Jede natürliche Zahl hat einen Rest, wenn sie durch 4 geteilt wird. Die möglichen Reste sind 0, 1, 2 und 3. Das bedeutet, dass jede natürliche Zahl in eine der vier Restklassen fällt: - Rest 0: \( n \equiv 0 \mod 4 \) - Rest 1: \( n \equiv 1 \mod 4 \) - Rest 2: \( n \equiv 2 \mod 4 \) - Rest 3: \( n \equiv 3 \mod 4 \) 2. **Anzahl der Zahlen**: Wenn wir 5 natürliche Zahlen haben, dann gibt es nur 4 verschiedene Restklassen (0, 1, 2, 3). 3. **Anwendung des Schubfachprinzips**: Da wir 5 Zahlen und nur 4 Restklassen haben, müssen mindestens zwei dieser Zahlen in der gleichen Restklasse liegen. Das bedeutet, dass für diese beiden Zahlen \( a \) und \( b \) gilt: \[ a \equiv b \mod 4 \] 4. **Differenz**: Wenn zwei Zahlen den gleichen Rest haben, dann ist ihre Differenz durch 4 teilbar: \[ 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.