Prove the Euclid division Lemma
Answers
A lemma is a proven statement used for proving another statement. So, according to Euclid's Division Lemma, if we have two positive integers a and b, then there would be whole numbers q and r that satisfy the equation: a = bq + r, where 0 ≤ r < b. a is the dividend. b is the divisor.
Answer:
We need to argue two things.
First, we need to show that q and r exist. Then, we need to show that q and r are unique.
To show that q and r exist, let us play around with a specific example first to get an idea of what might be involved, and then attempt to argue the general case.
Recall that if b is positive, the remainder of the division of b by a is the result of subtracting as many a's as are possible while still keeping the result non-negative.
If b is negative, the remainder is found in a slightly different way -- by adding as many a's as necessary until the result becomes non-negative.
With this in mind, suppose b=27 and a=5, and let us consider the set of all integers that results from either adding to 27, or subtracting from 27, some multiple of 5:
{…,−8,−3,2,7,12,17,22,27,32,37,…}
Now let us reduce this set down to just the positive values present, to produce a set
S={2,7,12,22,27,32,37,…}
We can see that the smallest element of this set (i.e., 2) is the remainder we seek -- but in the more general case, how can we be guaranteed that this smallest element exists? Recall the well-ordering principle tells us that any non-empty set of non-negative integers contains a least element. Perhaps this could prove helpful...
Now, with a hint of what tool might prove useful, let us turn our attention to the general case, for some arbitrary a and b, with a>0. In a manner similar to that employed above, we can construct a set
S={b−ka, where k is an integer and b−ka≥0}
We seek to show using the well-ordering principle that this set has a least element (which we hope will play the role of r). By its construction, S is only allowed to contain non-negative integers, so it remains to show that it is non-empty.
If b≥0, this is trivial, as b itself will be in the set (consider k=0).
If b<0, consider k=b instead. We aim to show that b−ka≥0 for this value of k and must then necessarily be in the set S. To this end, note
b−ka=b−ba=b(1−a)
and the factor (1−a) must be either zero or negative as a>0. Consequently b(1−a)≥0. Putting the left side of this last inequality back into its original form, we end up with b−ka≥0. Thus, we conclude S must contain the element b−ka when k=b.
So regardless of the value of b, S will have at least one element, and is thus non-empty. Having demonstrated that the set S is a non-empty set of non-negative values, the well-ordering principle applies and guarantees that S has a least element.
Now the question turns to whether or not this least element really is a reasonable value for r, and whether it can produce some reasonable value for q as well...
Suppose this least element is given by
r=b−kra
Of course, if this is to be a reasonable value for our purposes, we will need to be assured that 0≤r<a.
We already know r is non-negative as it was in S, so all we need to do now is assure ourselves that it is less than a. But consider the alternative: if r≥a, then b−kra≥a, which implies (after subtracting a from both sides) that
b−(kr+1)a≥0
This contradicts the fact that r was the smallest element of the set S. So it must be the case that r<a.
Finding q is now easy, as if b=qa+r, then
q=b−ra
Replacing r with b−kra, we have
q=b−(b−kra)a=kraa=kr
Thus, there exist integer values q and r, with 0≤r<a, such that b=qa+r.
It remains to show that these values for q and r are unique.
Effectively, we need to show that if b=q1a+r1 and b=q2a+r2, then it can only be the case that q1=q2 and r1=r2.
Without loss of generality, let us suppose that r2≥r1. Substituting for b, we have
q1a+r1=q2a+r2
But then
q1a−q2ar2−r1==r2−r1and thus,a(q1−q2)
Consequently, r2−r1 is some multiple of a.
However, since 0≤r1,r2<a and r2>r1, it must be the case that 0≤r2−r1<a. The only multiple of a in this range is zero, so r2−r1=0, or equivalently, r1=r2.
Further, as seen before,
q2=b−r2aandq1=b−r1a
Since r1 and r2 agree in value, this forces q1 and q2 to agree in value as well.
Thus, having shown that if b=q1a+r1 and b=q2a+r2, then it can only be the case that both q1=q2 and r1=r2, we can conclude that if there exist integers q and r such that b=qa+r with 0≤r<a, then those values of q and r are unique.
Since the first part of our argument established the existence of these integers q and r, we are done. It is indeed the case that given integers a and b, with a>0, there exist unique integers q and r such that b=qa+r and 0≤r<a.
Hope you got the answer......