Als Beispiel für eine mögliche Anwendung der Kongruenzrechnung werden hier mit deren Hilfe einige Teilbarkeitsregeln bewiesen.
In der Restklasse 
liegen alle ganzen Zahlen, die Vielfache von m sind. Deshalb kann man
die Teilbarkeitsrelation
in 
mithilfe
der Kongruenz wie folgt definieren:
In der Menge der Restklassen modulo
m werden eine Addition und eine Multiplikation
erklärt, die sich auf die Operationen der Repräsentanten stützen,
aber nicht von der Wahl der Repräsentanten abhängig sind:
Diese wichtige Eigenschaft der Restklassen bildet die Grundlage für
die Beweise der im Folgenden angeführten Teilbarkeitsregeln.
- Satz: Es sei
mit 
und 
Dann gilt:
(1)
genau dann, wenn 
mit 
und 
.
(2)
genau dann, wenn 
(wobei 
die Quersumme von z ist)
(3)
genau dann, wenn 
(wobei 
die alternierende Quersumme von z
ist)
Da 
mit 
gleichwertig ist, ergeben sich die genannten Teilbarkeitsregeln aus den
entsprechenden Kongruenzen.
Beweis von (1):
Aus 
folgt 
nach 
und damit 
,
d.h.:
Das ist gleichbedeutend mit 
Ganz analog erhält man aus 
die Relation 
und damit 
Aus 
folgt 
und damit 
Beweis von (2):
, da
aus 
die Relation 
folgt.
Gleiches gilt für die Kongruenz modulo 9.
Beweis von (3):
, da
aus 
die Relationen 
und 
folgen.
Die Teilbarkeitsregeln für 9 und 11
können auch für Rechenkontrollen
angewendet werden. Da 
ist, folgt aus 
,
dass 
ist. Das wird im Folgenden an zwei Beispielen demonstriert.
Anmerkung: Natürlich kann man statt 9
und 11 auch 2 und 3 oder 3 und 7 wählen, aber um eine Gleichheit
zu überprüfen ist die Wahrscheinlichkeit größer,
wenn sie bis auf Vielfache von 99 statt bis auf Vielfache von 6 oder 21
übereinstimmt.
- Beispiel 1:
Neunerprobe:
Elferprobe:
Es ist mit großer Wahrscheinlichkeit anzunehmen, dass richtig gerechnet
wurde.
- Beispiel 2:
Neunerprobe:
Wegen 
wurde hier mit Sicherheit falsch gerechnet.
Die Kongruenzrechnung ist auch ein wichtiges Hilfsmittel für die
Kalenderrechnung, worauf hier nicht
näher eingegangen werden wird. Aber die Tatsache, dass sich im Normalfall
(kein Schaltjahr) der zu einem Datum gehörende Wochentag von Jahr
zu Jahr um einen Tag verschiebt, ist aus der Kongruenzrechnung offensichtlich,
da 
ist.