- #1
snipez90
- 1,101
- 5
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 [tex]\leq[/tex] 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?
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 [tex]\leq[/tex] 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?
