Prove for natural numbers a and b, the greatest common divisor of a and b may be written as a linear combination of a and b.

Prove for natural numbers a and b, the greatest common divisor of a and b may be written as a linear combination of a and b. Or if d is the greatest common divisor of a and b GCD(a,b) there exist integers x and y such that

ax+ by = d

Let C be a set defined by z where z=ax+by for some integers x and y, and z is greater than 0. C is in the natural numbers and has a smallest element. m such that m=ax(0)+by(0). No we see that m < = a and m < = b because a(1) + b(0) and a(0) + b(1) are also in C. We will show that m=d. Since d divides a and d divides b, d divides ax(0) + by(0). Thus d divides m. Therefore d < = m.

Now the proof by contradiction...
suppose m does not divide a. Then by the division algorithm we proved yesterday there exist natural numbers q and r such that a=mq+r, where 0 < style="color: rgb(204, 0, 0);">m= ax(0) + by(0)
mq = aqx(0) + bqy(0)
a -r =aqx(0) + bqy(0)
r = a - aqx(0) - bqy(0)
r = a(1-qx(0) + b(-qy(0))

So r is a linear combination of a and b, so r is in our first set C. But r < style="color: rgb(204, 153, 51);">m < = d and as we proved earlier d <= m so d = m , so d (the GCD) can be written as a linear combination of a and b.

Prove if a and b are natural numbers with b < = a then there exists a q and r in the natural numbers such that a=qb +r.(Division Algorithm)

Prove if a and b are natural numbers with b < = a then there exists a q and r in the natural numbers such that a = qb + r and 0 < = r < b. Where q and r are the quotient and remainder. This is a proof of the division algorithm.

First we let T equal a number s in the natural numbers where a < sb. By the well ordering principle T has a smallest element which we can call w. Now we let q = w - 1 and r = a - qb since a > = b , w > 1 , q is in the natural numbers. Thus q < w , a > qb and r > = 0. By definition of r a = qb + r. Now suppose if r > = b. Then a - (w - 1)b > = b. so a >= wb, which contradicts the fact that a < wb. Therefore, r < b. In other words, the remainder should never be larger than the divisor. So r < b.