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.

Euclid's Algorithm: Let a and b be two positive integers with a <= b. Let d be their greatest common divisor(GCD). Then there are two lists of...

Euclid's algorithm is a way to find the GCD of any Euclidian domain, in this case, the natural numbers.

Euclid's Algorithm: Let a and b be two positive integers with a <= b. Let d be their greatest common divisor(GCD). Then there are two lists of positive integers q(i) and r(i) such that

b > r(1) > r(2) > r(3) ... > r(k-1) > r(k) > r(k+1) = 0 and

a = bq(1) + r(1)
b = r(1)q(2) + r(2)
r(1) = r(2)q(3) + r(3)
r(2) = r(3)q(2) + r(4)
.
.
.
r(k-2) = r(k-1)q(k) + r(k)
r(k-1) = r(k)q(k+1) (that is, r(k+1) = 0 )

and therefore d = r(k)

Proof

Since a < = b then there exists a q(1) and r(1) such that a = bq(1) + r(1) where 0 < = r(1) < b , and therefore, since r(1) < b there exists a q(2) and r(2) such that b=r(1)q(2) + r(2) and so one for r(2)< r(1). If we keep going down the line of positive integers we reach a point were r(k+1)=0 and so it is evident that:

b > r(1) > r(2) > r(3) ... > r(k-1) > r(k) > r(k+1) = 0

Now, to show that d (the GCD) is equal to r(k) we have to show that r(k) < = d and r(k) > = d.

First we show that r(k) < = d.

We first notice that r(k) divides r(k-1) (because r(k-1) = r(k)q(k+1)), we also notice that r(k) divides r(k-2) because r(k-2) = r(k-1)q(k) + r(k), and so r(k) divides both r(k) and r(k-1) by the proof we did two days ago. (When another proof is used in a proof, it is called a lemma). Now, if we keep going up the line, we see that every number has a component of the previous integer, and so r(k) is a common divisor for all the numbers including a and b. Since d is the GCD for a and b, then r(k) has to be < = d by the proof we did yesterday.

Now we show that r(k) > = d.

We note that d divides r(1) since r(1) = a - bq(1), and since d divides r(1) then by the proof we did two days ago, d also divides r(2) since r(2) = b - r(1)q(2), continuing this pattern down the line we see that d divides r(k-1) and r(k) and therefore r(k) > = d.

Now we can say that d= r(k) which is equal to 1, and 1 is the GCD of all positive integers, or the natural numbers.

Let d be the greatest common divisor of two positive integers a and b. If c is a positive integer such that c divides a ,and c divides b, then c <= d

Let d be the greatest common divisor of two positive integers a and b. Prove if c is a positive integer such that c divides a ,and c divides b, then c <= d.

This is a somewhat simple proof since it uses the definition of a greatest common divisor.

A greatest common divisor (GCD) is the largest integer which divides two other integers. Take for example the numbers 24 and 16. 8 is the GCD for 24 and 16 since 8 is the largest number that will divide both of them.

So if the GCD=d then d divides a, and d divides b.

The numbers 4 and 2 also divide 24 and 16, but are not the "Greatest". However, we do see that 4 and 2 also divide 8, which is the second part of the definition of a GCD.

For every positive integer c, if c divides a and c divides b, then c divides d.

It is this last part of the definition we will use for our proof. If c is an integer which divides a and b, then by definition c must also divide the GCD, which is d. And therefore c < d. ~~~~