The quotient remainder theorem (article) | Khan Academy (2024)

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

The quotient remainder theorem (article) | Khan Academy (2024)

FAQs

The quotient remainder theorem (article) | Khan Academy? ›

When we want to prove some properties about modular arithmetic

modular arithmetic
In mathematics, modular arithmetic is a system of arithmetic for integers, where numbers "wrap around" when reaching a certain value, called the modulus. The modern approach to modular arithmetic was developed by Carl Friedrich Gauss in his book Disquisitiones Arithmeticae, published in 1801.
https://en.wikipedia.org › wiki › Modular_arithmetic
we often make use of the quotient remainder theorem. It is a simple idea that comes directly from long division. 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.

What is the quotient remainder theorem? ›

The quotient-remainder theorem says that when any integer n is divided by any pos- itive integer d, the result is a quotient q and a nonnegative remainder r that is smaller than d. n = dq + r and 0 ≤ r < d.

How do you use the remainder theorem to find the remainder? ›

The remainder theorem states that when a polynomial p(x) is divided by (x - a), then the remainder = f(a). This can be proved by Euclid's Division Lemma. By using this, if q(x) is the quotient and 'r' is the remainder, then p(x) = q(x) (x - a) + r.

What is the remainder theorem in Algebra 2? ›

Remainder Theorem is an approach of Euclidean division of polynomials. According to this theorem, if we divide a polynomial P(x) by a factor ( x – a); that isn't essentially an element of the polynomial; you will find a smaller polynomial along with a remainder.

What is the remainder value theorem? ›

The Remainder Theorem tells us that, in order to evaluate a polynomial p(x) at some number x = a, we can instead divide by the linear expression x − a. The remainder, r(a), gives the value of the polyomial at x = a.

What is the quotient remainder rule formula? ›

The dividend divisor quotient remainder formula can be applied if we know either the dividend or remainder or divisor. The formula can be applied accordingly. For dividend, the formula is: Dividend = Divisor × Quotient + Remainder. For divisor, the formula is: Dividend/Divisor = Quotient + Remainder/Divisor.

What is remainder theorem with example? ›

Remainder Theorem Examples

Solution: Consider the value of a to be 4. Therefore, f ( 4 ) = 0. Remainder Theorem is a way of addressing Euclidean's division of polynomials. It states that when a polynomial is p(a) is divided by another binomial (a – x), then the remainder of the end result that is obtained is p(x).

What are the rules for the remainder theorem? ›

The remainder theorem states that when a polynomial, f(x), is divided by a linear polynomial , x - a, the remainder of that division will be equivalent to f(a).

How can you apply remainder theorem in real life? ›

Real-life Applications
  1. The remainder theorem provides a more efficient avenue for testing whether certain numbers are roots of polynomials.
  2. This theorem can increase efficiency when applying other polynomial tests, like the rational roots test.

What is the remainder theorem for dummies? ›

Summary – Remainder Theorem

It states that when a polynomial P(x) is divided by a linear polynomial x – a, the remainder is equivalent to P(a). This theorem simplifies polynomial evaluation by allowing one to find the remainder of a division by directly substituting a value into the polynomial.

Why do we use the remainder theorem? ›

The remainder theorem can be used when you want to find the remainder of a polynomial division. In other words, it can be used to determine the remainder when a polynomial is divided by another polynomial. The remainder theorem is also sometimes referred to as the polynomial remainder theorem.

Does the remainder theorem work? ›

The reminder theorem is only true when the divisor is a linear polynomial. That means it cannot be utilized when the divisor is something else and if the degree of the divisor polynomial is more than 1 , the sole way to find the remainder is polynomial long division.

What is the logic behind remainder theorem? ›

Answer: According to the remainder theorem, if polynomial f(x) is divided by a linear binomial of the variable (x – a) then the remainder will be f(a). On the other hand, factor theorem states that if f(a) = 0 in this case then the binomial (x -a) is a factor of polynomial f(x).

How to find factors of a polynomial using the remainder theorem? ›

The remainder theorem says that when dividing a polynomial f(x) by x - a, the remainder will be equal to f(a). The factor theorem says that if f(a) = 0 then x - a is a factor of the polynomial f(x). Putting these two theorems together tells us that if the remainder is 0 then we have found a factor of the polynomial.

What are the properties of the remainder theorem? ›

Properties of a Remainder

A remainder is always less than the divisor. If one number (divisor) divides the other number (dividend) completely, then the remainder is 0. It is referred to as a complete division. If a dividend is a multiple of the divisor, then the remainder is 0.

What is the quotient the remainder? ›

The quotient is the number of times a division is completed fully, while the remainder is the amount left that doesn't entirely go into the divisor. For example, 127 divided by 3 is 42 R 1, so 42 is the quotient, and 1 is the remainder.

How does the Chinese remainder theorem work? ›

In mathematics, the Chinese remainder theorem states that if one knows the remainders of the Euclidean division of an integer n by several integers, then one can determine uniquely the remainder of the division of n by the product of these integers, under the condition that the divisors are pairwise coprime (no two ...

What is the quotient and remainder solution? ›

The formula for Quotient = Dividend ÷ Divisor. In Mathematics, the remainder is the amount "left over" after performing some computation. In arithmetic, the remainder is the integer "left over" after dividing one integer by another to produce an integer quotient.

Top Articles
Latest Posts
Recommended Articles
Article information

Author: Aracelis Kilback

Last Updated:

Views: 5273

Rating: 4.3 / 5 (64 voted)

Reviews: 87% of readers found this page helpful

Author information

Name: Aracelis Kilback

Birthday: 1994-11-22

Address: Apt. 895 30151 Green Plain, Lake Mariela, RI 98141

Phone: +5992291857476

Job: Legal Officer

Hobby: LARPing, role-playing games, Slacklining, Reading, Inline skating, Brazilian jiu-jitsu, Dance

Introduction: My name is Aracelis Kilback, I am a nice, gentle, agreeable, joyous, attractive, combative, gifted person who loves writing and wants to share my knowledge and understanding with you.