# 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**