# Three corollaries to a well-known theorem

1. Aug 23, 2008

### snipez90

Hello, I need help verifying a few corollaries that follow from the following proof. I will attempt to reconstruct the proof as given in the textbook. Although the theorem is not particularly intuitive, at least to me, I think I fully understand it.

Theorem: Let g be the greatest common divisor of integers a and b and denote it (a,b). Prove that there exist integers x1 and y1 such that g = (a,b) = a*x1 + b*y1.

Proof:

Consider the linear combinations ax + by where x,y range over all integers. Fix a and b. This set of integers contains negative and positive values, as well as 0 by the choice x = y = 0. There must exist a least positive value L in the set and let L = a*x1 + b*y1.

Now we show that L|a and L|b. Assume on the contrary that L does not divide a. Then there exists positive integers q and r such that a = qL + r where 0 < r < L. Then we have r = a - qL = a - q(a*x1 + b*y1) = a(1-q*x1) + b(-q*y1). Hence r is also a member of the set ax + by, which contradicts the minimality of L. Thus L|a. Similarly, we can show that L|b.

Since g is the greatest common divisor of a and b, there exists integers A and B such that a = gA and b = gB. Then we have L = a*x1 + b*y1 = g(A*x1 + B*y1), which implies that g|L. Since g > 0, L > 0, g $$\leq$$ L. If g < L, then we have a contradiction since g is the greatest common divisor of a and b(remember, L|a and L|b). Thus g = L = a*x1 + b*y1. QED.

Now for the three corollaries:
1. The (a,b), the gcd of a and b, is the least positive value of ax + by where x and y are integers.
2. (a,b) is the common divisor of a and b that is divisible by every common divisor
3. If an integer h is expressible as h = ax + by, then h is not necessarily (a,b) but (a,b)|h and particularly if h = 1, then (a,b) = 1.

The second corollary is most intuitive I think. To prove it, suppose d is any common divisor of a and b. Then d|a and d|b which implies that d|(ax + by). Thus we can choose x and y such that d|(a,b).

In fact, now that I take a closer look, the proofs for the second and third corollary rely on essentially the same property I think? Let g = (a,b) then g|a and g|b so g|(ax+by). Since ax + by = h, g|h. If h = 1, and g > 0, then g = (a,b) = 1.

Then that just leaves the first corollary. I think I'm confused. Does it immediately follow from the proof? In the proof, I assumed L was the least positive linear combination ax + by and deduced that it equaled the gcd so logically the corollary must follow?

2. Aug 24, 2008

### tiny-tim

corollaries

Hi snipez90!

Corollaries are usually such easy proofs that they don't deserve to be recognised as separate theorems.

In this case, it follows from the definition of g:

g divides both a and b, so it divides all ax + by, so they can't be less than g.

3. Aug 25, 2008

### snipez90

Hmm, thanks for that perspective. Now the theorem is intuitive after all and the motivation behind the initially mysterious proof is clear.

I think I'll try not to get too caught up on my "formal" textbook heh.