Teorema împărțirii cu rest

Atunci când vrem să demonstrăm anumite proprietăți ale aritmeticii modulare folosim adesea teorema împărțirii cu rest. Este o idee simplă care provine direct din împărțirea de numere întregi mari (noi îi mai spunem și împărțirea lungă).

Teorema împărțirii cu rest spune că:
Fiind date un număr întreg oarecare A și un întreg pozitiv B, există numerele întregi unice Q și R astfel încât

Se poate observa că această proprietate este derivată din algoritmul de împărțire a numerelor mari. Atunci când împărțim A la B, Q este câtul și R este restul. Dacă putem scrie un număr în forma aceasta atunci 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