Die Kongruenznotation

Kongruenznotation und sichere Rechenregeln · Abschnitt 5 von 64

Intuition

Gleichheit der Reste

$aequiv bpmod m$ sagt nicht, dass $a=b$ ist. Es sagt: Beide Zahlen liegen im selben Restfach modulo $m$ – wie 3 und 15 auf einer 12-Stunden-Uhr.

Definition

Kongruenz modulo m

Für $m>0$ gilt $a\equiv b\pmod m$ genau dann, wenn $m\mid(a-b)$ . Gleichwertig besitzen $a$ und $b$ denselben Standardrest modulo $m$ .

Gelöstes Beispiel

Beispiel mit 38 und 3

$38\equiv3\pmod5$ , weil $38-3=35$ durch 5 teilbar ist.

Typischer Fehler

Kongruent ist nicht gleich

Aus $a\equiv b\pmod m$ folgt im Allgemeinen nicht $a=b$ . Erst eine zusätzliche Schranke, etwa $0\le a,b<m$ , macht die Vertreter eindeutig.