Factoring binomials using the greatest common factor

One way to factor binomials is by searching for the greatest common factor.

Consider

(5x * 25)

In this case the greatest common factor is 5 and the phrase can be written as

5(x*5)

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.

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

Prove if c divides a and c divides b, then c divides any combination an+bm, where n and m are integers

Prove if c divides a and c divides b, then c divides any combination an+bm, where n and m are integers.

Since c divides both a and b then there must exist integers j and t such that a=cj and b=ct.

So by substitution into an+bm we get

an+bm = (cj)n+(ct)m = c (jn + tm). So c divides (an + bm) ~~~~

Thus, if c divides a and b, then c also divides any multiple of a and b.