> For the complete documentation index, see [llms.txt](https://calnix.gitbook.io/zk-notes/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://calnix.gitbook.io/zk-notes/abstract-math/modular-arithmetic/the-quotient-remainder-theorem.md).

# 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\
\&#xNAN;**`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**

{% hint style="info" %}
Q is quotient, B is divisor. The remainder when A/B is R => A mod B = R
{% endhint %}