1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
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.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook