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.

Main content

# 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?
(30 votes)
• 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
(133 votes)
• Is this the same as Euclid's Division Lemma?
(7 votes)
• 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?
(2 votes)
• 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
(3 votes)
• show that one and only one out of n,n+2 or n+4 is divisible by 3
(2 votes)
• 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
(3 votes)
• if -16 mod 26 = 10, then how is the quotient -1?
(2 votes)
• If you multiply the integer quotient by the divisor and then add the remainder (mod), you get the original number.

-16 (original number) divided by 26 (divisor) gets a quotient of -1 with a remainder of 10. The inverse is -1 (quotient) * 26 (divisor) + 10 (remainder) = -26+10= -16 (original number)
(3 votes)
• 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
(2 votes)
• 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} ?
(2 votes)
• 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)
• It means that for a given pair (A,B) there exists only one pair (Q,R).
e.g.
17/3= 5 R 2
in this case (A,B)=(17,3) and (Q,R)=(5,2)
If (Q,R) was not unique then there would be some other answer to 17/3. There is not.
In reality, there is exactly one answer, for A/B.

A proof of this is posted in the comments section.
(3 votes)
• if n is divided by 4 the reminder is 3 then 2n divide by 4 the reminder is
(2 votes)
• n=4c+3 (c is a constant)
2n=8c+6
2n=4(2c+1)+2
2n=4d+2 (d is another constant)

remainder=2
(1 vote)
• guise im wondering what DIV is in computere science I got question in exam: 26 DIV 6 can someone please take me by the hand and guide me through dis
(1 vote)
• DIV is integer division (which chops off or rounds down, the fractional amount)
It is the the quotient you get when you perform long division.

e.g.
26 / 6 = 4 with a remainder of 2
So:
26 div 6 = 4
26 mod 6 = 2

In computers, when you perform division, the hardware figures out both the div and mod at the same time (but they behave a bit strangely for negative numbers, because of how we represent negative numbers on computers).
(2 votes)