Main content

## Computer science

### Unit 2: Lesson 5

Modular arithmetic- What is modular arithmetic?
- Modulo operator
- Modulo Challenge
- Congruence modulo
- Congruence relation
- Equivalence relations
- The quotient remainder theorem
- Modular addition and subtraction
- Modular addition
- Modulo Challenge (Addition and Subtraction)
- Modular multiplication
- Modular multiplication
- Modular exponentiation
- Fast modular exponentiation
- Fast Modular Exponentiation
- Modular inverses
- The Euclidean Algorithm

© 2023 Khan AcademyTerms of usePrivacy PolicyCookie Notice

# The quotient remainder theorem

## The quotient remainder theorem

When we want to

It is a simple idea that comes directly from

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

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

If we can write a number in this form then

**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(125 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)

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

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)