Das Quotientenrest-Theorem

Wenn wir einen Beweis einiger Eigenschaften der modularen Arithmetik machen wollen, benutzen wir oft die Division mit Rest.
Es ist eine einfache Idee, die direkt von der schriftlichen Division herrührt.

Die Division mit Rest besagt:
Für jede ganze Zahl A und eine zweite positive ganze Zahl B, existieren die eindeutigen ganzen Zahlen Q und R für die gilt

Wie wir sehen entstammt diese Formel direkt der schriftlichen Division. Wenn wir in der schriftlichen Division A durch B teilen, ist Q der Quotient und R ist der Rest.
Wenn wir eine Zahl in dieser Form schreiben wollen, dann ist A mod B = R

A = 7, B = 2

7 = 2 * 3 + 1
7 mod 2 = 1

A = 8, B = 4

8 = 4 * 2 + 0
8 mod 4 = 0

A = 13, B = 5

13 = 5 * 2 + 3
13 mod 5 = 3

A = -16, B = 26

-16 = 26 * -1 + 10
-16 mod 26 = 10