Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Three corollaries to a well-known theorem

  1. Aug 23, 2008 #1
    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.


    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?
  2. jcsd
  3. Aug 24, 2008 #2


    User Avatar
    Science Advisor
    Homework Helper


    Hi snipez90! :smile:

    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. :smile:
  4. Aug 25, 2008 #3
    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.
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?

Similar Discussions: Three corollaries to a well-known theorem
  1. Well ordering (Replies: 1)

  2. Three forms (Replies: 3)

  3. Largest Known Prime (Replies: 20)