O teorema do resto do quociente

Quando queremos provar algumas propriedades sobre aritmética modular nós muitas vezes usamos o teorema quociente-resto.
É uma ideia simples que vem direto da divisão longa.

O teorema quociente-resto diz:
Dado qualquer número inteiro A, e um número positivo inteiro B, existem inteiros únicos Q e R tal que

Podemos ver que isso vem diretamente de divisão longa. Quando dividimos A por B na divisão longa, Q é o quociente e R é o resto.
Se podemos escrever um número nesta forma, então 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