Twierdzenie o reszcie z dzielenia

Często udowadniając jakieś własności dotyczące arytmetyki modularnej używamy twierdzenia o dzieleniu z resztą.
To prosty pomysł pochodzący bezpośrednio z algorytmu dzielenia pod kreską.

Treść twierdzenia o dzieleniu z resztą jest następująca:
 Dla każdej liczby całkowitej A i każdej liczby naturalnej B, istnieją jednoznacznie wyznaczone liczby całkowite Q oraz R spełniające równanie

Twierdzenie to pochodzi dokładnie z algorytmu dzielenia pisemnego, albo "dzielenia pod kreską". Kiedy dzielimy A przez B, Q nazywa się ilorazem a R nazywa się resztą z dzielenia.
 Oczywiście, prawdziwe jest równanie 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