If you're seeing this message, it means we're having trouble loading external resources for Khan Academy.

If you're behind a web filter, please make sure that the domains *.kastatic.org and *.kasandbox.org are unblocked.

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

Examples

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