Math, asked by krishnakundankumar86, 6 months ago

Prove the Euclid division Lemma​

Answers

Answered by Anonymous
0

{\huge {\underline {\purple {\mathbb{ANSWER}}}}}

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.

Answered by swathi21025
0

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

Similar questions