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?

  • leaf green style avatar for user SteveSargentJr
    Have you proven the Quotient Remainder Theorem previously?
    (30 votes)
    Default Khan Academy avatar avatar for user
    • male robot hal style avatar for user Cameron
      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
      (125 votes)
  • leafers ultimate style avatar for user Shreyas Pai
    Is this the same as Euclid's Division Lemma?
    (7 votes)
    Default Khan Academy avatar avatar for user
  • blobby green style avatar for user Msule Mshindo
    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)
    Default Khan Academy avatar avatar for user
    • male robot hal style avatar for user Cameron
      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)
  • leaf green style avatar for user Jeelani Mudassir
    show that one and only one out of n,n+2 or n+4 is divisible by 3
    (2 votes)
    Default Khan Academy avatar avatar for user
    • leafers ultimate style avatar for user deeksha.vs
      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)
  • leaf green style avatar for user Dinithi Navarathna
    if -16 mod 26 = 10, then how is the quotient -1?
    (2 votes)
    Default Khan Academy avatar avatar for user
    • male robot hal style avatar for user Lars Opstad
      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)
  • blobby green style avatar for user Alameen Ameen
    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)
    Default Khan Academy avatar avatar for user
    • male robot hal style avatar for user Cameron
      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)
  • blobby green style avatar for user hulibandikud
    Why doesn't the Euclid division algorithm work for numbers "n" where n={x:x is a set containing all negative integers} ?
    (2 votes)
    Default Khan Academy avatar avatar for user
  • female robot grace style avatar for user gunwati.rules
    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)
    Default Khan Academy avatar avatar for user
    • male robot hal style avatar for user Cameron
      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)
  • blobby green style avatar for user suhan.tripathy
    if n is divided by 4 the reminder is 3 then 2n divide by 4 the reminder is
    (2 votes)
    Default Khan Academy avatar avatar for user
  • blobby green style avatar for user Monica C.
    I'm so confused... I don't understand any of this. :( What does mod mean?
    (1 vote)
    Default Khan Academy avatar avatar for user
    • leafers tree style avatar for user Jordan Nguyen
      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?***
      It's because you modded your 7 (your dividend) by 3 (your divisor), that you end up with 1 (your remainder).

      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

      I hope this helps!
      (2 votes)