⠀

Proposition: Die "Teilt-mit-selbem-Rest-Relation" ist eine Äquivalenzrelation

Es seien

sowie

.

Dann sei die Teilt-mit-selbem-Rest-Relation, also:

Beweis

Was bedeutet dann diese kryptische Gleichung? Nun, wir können sie einmal wie folgt umstellen:

oder in anderen Worten: teilt ganzzahlig mit Rest .

Um zu zeigen, dass eine Äquivalenzrelation ist, müssen wir zeigen, dass folgende Eigenschaften hat:

Beweis der Reflexivität Es ist zu zeigen, dass . Wir setzen ein und stellen etwas um:

Wir wählen woraus folgt , die Gleichung gilt.

Beweis der Symmetrie Es ist zu zeigen, dass .

Es gelte hierzu . Dann gibt es ein mit

Wir müssen zeigen, dass es ein gibt, mit . Dieses ist einfach , denn .

Beweis der Transitivität Es ist zu zeigen, dass .

Das heißt, es gibt ein mit .

Es gelte hierzu und . Dann gibt es mit und

Wir stellen den letzten Term etwas um:

und ersetzen in der ersten Gleichung:

Wir haben also

Fazit Wir haben zeigen können, dass reflexiv, symmetrisch und transitiv ist. Daher handelt es sich bei um eine Äquivalenzrelation.