The quotient remainder theorem

When we want to prove some properties about modular arithmetic we often make use of the quotient remainder theorem. It is a simple idea that comes directly from long division.

The quotient remainder theorem says:

Given any integer A, and a positive integer B, there exist unique integers Q and R such that A = B * Q + R, where 0 ≤ R < B

We can see that this comes directly from long division. When we divide A by B in long division, Q is the quotient and R is the remainder. If we can write a number in this form then A mod B = R

Q is quotient, B is divisor. The remainder when A/B is R => A mod B = R