If you're seeing this message, it means we're having trouble loading external resources on our website.

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

# The quotient remainder theorem

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

## Want to join the conversation?

• Have you proven the Quotient Remainder Theorem previously? •   Here's the proof.

Proof of the Quotient Remainder Theorem

We want to prove:
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 have to prove two things:
Given any integer A and positive integer B:
1) Q and R exist
2) Q and R are unique

Proof that Q and R exist

(One approach is to use the Well Ordering Principle of Integers, but I will use an approach that is arguably simpler)
Suppose we have an integer A and a positive integer B.
Given any real number A and any positive real number B if I divide A by B, I will have an integer part (before the decimal),w, and a fractional part,f, after the decimal.

If A is >= 0 then w and f are non-negative:
A/B = w + f where 0 ≤ f < 1
A = B * w + B * f
w is an integer (it is the whole part) we can simply label it as Q, i.e. Q = w

by multiplying 0 ≤ f < 1 by B we find that
B * 0 ≤ B * f < B * 1
0 ≤ B * f < B
we can simply label the term B * f as R i.e. R= B * f
We have shown that 0 ≤ R < B
To show that R is an integer we can say that:
A = B * w + B * f
A = B * Q + R (using our new labels)
we can rearrange this to:
R = A - B * Q
but A, B, Q are integers and the result of any integer minus the product of integers is still an integer (this a property of integers)
so R must be an integer

so we have shown that given any integer A >= 0 and any positive integer B, there exist integers Q and R such that: A= B * Q + R where 0 ≤ R < B

if A is negative then
A/B = w + f where -1 < f ≤ 0
A = B * w + B * f

if f = 0 then label w as Q and B * f as R
A = B * Q + R
since B * f = R = 0 we can say that R satisfies 0 ≤ R < B
and that R is an integer

if -1 < f < 0
A = B * w + B * f
A = B * ( w - 1) + B * (f + 1)
label w-1 as Q, which is an integer

add 1 to -1 < f < 0
0 < f + 1 < 1
multiply by B
0 < B * ( f + 1 ) < B
we can simply label the term B * (f + 1) as R
We have shown that 0 < R < B which satisfies 0 ≤ R < B

To show that R is an integer, in this case, we can say that:
A = B * ( w - 1) + B * (f + 1)
A = B * Q + R (using our new labels)
we can rearrange this to:
R = A - B * Q
but A, B, Q are integers and the result of any integer minus the product of integers is still an integer (this a property of integers)
so R must be an integer

so we have shown that given any integer A < 0 and any positive integer B, there exist integers Q and R such that: A= B * Q + R where 0 ≤ R < B

so we have shown that given any integer A and any positive integer B, there exist integers Q and R such that: A= B * Q + R where 0 ≤ R < B

Proof that Q and R are unique

Suppose we have an integer A and a positive integer B.
We have shown before that Q and R exist above.
So we can find at least one pair of integers, Q1 and R1, that satisfy
A= B * Q1 + R1 where 0 ≤ R1 < B
And we can find at least one pair of integers, Q2 and R2, that satisfy
A= B * Q2 + R2 where 0 ≤ R2 < B

For labeling purposes, R2 is >= than R1 (if not we could just switch the integer pairs around).
We will show that Q1 must equal Q2 and R1 must equal R2 i.e. Q and R are unique

We can set the equations equal to each other
B * Q1 + R1 = B * Q2 + R2
B * (Q1 - Q2) = (R2 - R1)
(Q1 - Q2) = (R2 - R1)/ B

since R2 >= R1 we know that R2 - R1 is >= 0
since R2 <B and R1 >= 0 we know that R2-R1 < B
So we can say that 0 ≤ R2 - R1 < B
divide by B
0 ≤ (R2 - R1)/B < 1
but from above we showed that
(Q1 - Q2) = (R2 - R1)/ B
and Q1 - Q2 must be an integer since an integer minus an integer is an integer
so (R2 - R1)/B must be an integer but its value is >= 0 and < 1.
The only integer in that range is 0.
So (R2- R1)/B= 0 ,thus R2-R1 =0 ,thus R2 = R1
also
Q1-Q2 = 0 thus Q1 = Q2

Thus we have shown that Q1 must equal Q2 and R1 must equal R2 i.e. Q and R are unique

Hope this makes sense
• Is this the same as Euclid's Division Lemma? • if n is divided by 3 remainder is 2,if n is divided by 5 remainder is 1,what is the least value of n? • We have
n mod 3 = 2
n mod 5 = 1
3 and 5 are coprime so we can use the Chinese Remainder Theorem

By the Chinese Remainder Theorem:
Given
n mod x = a
n mod y = b
where x and y are coprime, we have:
n = (y * (y^-1 mod x) * a + x * (x^-1 mod y) * b ) mod (x * y)
n = (5 * (5^-1 mod 3) * 2 + 3 * (3^-1 mod 5) * 1 ) mod (3 * 5)
n = 5 * 2 * 2 + 3 * 2 * 1 mod 15
n = 26 mod 15
n = 11
• show that one and only one out of n,n+2 or n+4 is divisible by 3 • Taking divisibility of numbers by 3, numbers can be expressed in 3 forms: 3q,3q+1,3q+2
(where q is the quotient obtained on dividing by 3 and 1,2 are the remainders)
Let us take Case1: n=3q
n+2 will be3q+2 and n+4=3q+4
Hence only n is divisible by3
Case2: n=3q+1
n+2=(3q+1)+2=3q+3=3(q+1)
n+4=(3q+1)+4=3q+5
Hence n+2 is divisible by 3
Similarly we can apply n=3q+2 to get n+4 divisible by 3
• if -16 mod 26 = 10, then how is the quotient -1? • I have the following question please , How can I calculate -24 mod 23 ? if i apply the theorem of the reminder then R= -1 but the theorem reads that R >= 0
Also what about if we have 0.25 mod 23 how can you solve it? in other words can we find the mod for not integer numbers . Thanks for any help • We want to write:
A = B * Q + R where 0 <= R < B

Doing long division the correct way (remembering that R >= 0):
-24/23 = -2 R 22

From this, we can see that:
-24 = 23 * -2 + 22
Thus -24 mod 23 = 22

We can still recover from doing long division the incorrect way (forgetting that R >= 0):
-24/23 = -1 R -1 (oops!)

This shows us that:
-24 = 23 * -1 + -1
We can add 23 to the second term and subtract it from the first term on the right hand side (since 23 - 23 is 0)
-24 = (23 * -1 - 23) + (-1 + 23)
-24 = 23 * -2 + 22
Now it's in the form we want.
Thus -24 mod 23 = 22

With regards to 0.25 mod 23:
- modular arithmetic is not applicable to non-integer numbers

In case you were wondering, the modulus must be >0 as well ( So 5 mod -23 doesn't make sense either)

Hope this makes sense
(1 vote)
• Why doesn't the Euclid division algorithm work for numbers "n" where n={x:x is a set containing all negative integers} ? • What does it mean if Q and R are unique? That Q and R are different, or that for every pair of integers (A, B), there exists only one pair (Q,R)? I don't see how either of those are true.
(1 vote) • if n is divided by 4 the reminder is 3 then 2n divide by 4 the reminder is • I'm so confused... I don't understand any of this. :( What does mod mean?
(1 vote) • modulo (or mod) is the modulus operation very similar to how divide is the division operation. When you divide, you're finding the quotient. When you mod, you're finding the remainder.

Think of the fraction `7/3`, or seven divided by three. It's the same as `2 + 1/3`, or two and a third.
***Now, where did the two come from?***
It's because you divided 7 (your dividend) by 3 (your divisor) that you end up with 2 (your quotient).
***Now, where did the third come from?***
So 7 divided by 3 is 2, or `7/3=2` (strict integer division), while 7 mod 3 is one, or `7 mod 3=1`