Question 847198: prove eucalid division
Answer by swincher4391(1107)   (Show Source):
You can put this solution on YOUR website! First we want to show that there exists two integers q and r such that a = bq+r where 0 <= r < b and that q and r are unique.
Let's look at r for a minute. Rearranging gives us a-bq. Let's create a set such that a-bq >=0. Call this set A. Since a,b,q are all integers, we know a-bq must be an integer as well. We plan to use the Well-Ordering Principle. We know that A is a set of non-negative integers. We must also show that A is not empty. There are two cases:
a>0 then we have a is inside of A. Done.
a<0 then we have a-ba = -a(b-1) = |a|(b-1) is in A (notice we chose q = a which is perfectly fine). By our assumption we know b>0 so b-1 >= 0. Then we have that By the Well-Ordering principle, A must have smallest element which guarantees a-bq >= 0.
At this point we make a claim hoping it logically follows.
Let's claim that a-bq < b :
In hopes of a contradiction, we say that that a-bq >= b. This would mean that a-bq -b = 0. Then a-b(q+1) >= 0. But (a-b)(q+1) is smaller than a-bq which violates what we just proved about A. Thus we have a contradiction and thus a-bq < b.
We now hope to prove uniqueness. So let's look at a-bq one more time but assign it to r. Then we have that a = bq+a-bq = bq+r.
Usually to prove uniqueness, we assume that another q and r exist. That's what we will do. Let's rename our original q and r to be q1 and r1 and claim there exists a q2 and r2 that work as well.
So let there be a (q1,r1) and (q2,r2) exist such that
a= bq1+r1 = bq2+r2 (that's what we mean by more than one solution)
Then a direct consequence is that b(q1-q2) = (r2-r1). This means that b divides r2-r1. Can this happen though? Think about r2-r1, it could only possibly range as -b < r2-r1 < b [since each range from 0 to b]. The only possible way this could work is if r2-r1 = 0. This means that r1=r2 so r is unique.
So we have bq1 + r = bq2+r. By consequence this means bq1 = bq2 so q1=q2 so q is unique.
We have proven Euclid's Division Algorithm.
|
|
|
