Теорема за остатъка от делене

Когато искаме да докажем някакви свойства за модулната аритметика, често използваме теоремата за делене с остатък.
Това е проста идея, която идва пряко от дългото делене.

Теоремата за делене с остатък гласи:
За всяко цяло число A и положително цяло число B съществуват единствени цели числа Q и R, за които

Може да забележим, че това идва директно от алгоритъма за деление на многоцифрени числа. Когато делим A на B с този алгоритъм, Q е частното, а R – остатъкът.
  Ако можем да запишем число в този вид, тогава 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