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