Here's the proof. Proof of the Quotient Remainder Theorem We want to prove: We have to prove two things: 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)
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
Given any integer A and positive integer B:
1) Q and R exist
2) Q and R are unique
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
