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

Theorem 1.2.1. Common Divisor

  1. Jun 21, 2012 #1
  2. jcsd
  3. Jun 21, 2012 #2
    Hi hawaiifiver, which part are you struggling with ?

    The theorem says that for any pair of integers a and b, there exist a third integer d, called common divisor of a and b, d being written as a linear combination of a and b: d=ax+by, x and y being integers

    this is true for any pair of integers, but first it is proved for positive integers, a and b >=0 (in fact a>=b>=0, it doesn't matter since both are arbitrary and you could always rename a to b and b to a)

    so suppose you have a and b given
    just two integers, you only require that they are both >=0 and you name a the biggest of the two, b the other
    from there, you name n the sum a+b

    first case, n=0 there is only way: both a and b are 0 and clearly the theorem is true, because d=0 works and any x and y gives you 0*x+0*y=0

    then, induction, supposing the theorem is true up to n-1
    if b=0, then d=a works with x=1, this is still trivial
    else, if b >=1, then, you know that (since the theorem was supposed to be true up to n-1)
    there exist x and y so that d=(a-b)x+by because (a-b)+b=n-b which is <=n-1 (because we are looking at the case b>=1, and therefore we use it to find some combination using b that is a sum of a+[something] that is <=n
    so, d=(a-b)x+by exists
    so d=ax+(y-x)b and so we have proved that for a+b>=0, there is such a d by induction

    the next step is to say that if it is true for any positive a and b, then if a or b are negative, it will work for their absolute values, but then it is a trivial combination to get back to their negative values

    Don't know if it helps, it would be better if you precised what is not clear about it so as to be more verbose on the important part

  4. Jun 22, 2012 #3
    Hi oli4. Thanks for the swift reply

    There are a few things I don't understand

    1. Where did they get n = a +b from. Why is that important?

    2. When they say assume that the theorem has been proved up to n-1, why do they choose n -1

    3. Why do they apply the theorem to (a-b) and (b). I don't understand where they get that from.

  5. Jun 22, 2012 #4
    Hi Hawaiifiver
    1. they didn't get it from anywhere, they 'set it', this is a sort of trick to make the problem involving 2 integers reduced to one integer (the sum of the other two)

    2. This is a common technique for proof by induction
    The idea is this:
    You want to show that some property of n is valid for all possible values of n
    First, you verify that it is true for 0, or 1 (it depends on where it starts, it could be true for all values >0, or >whatever, and you start from the first value that mus be ok). in this case, 0
    Second, you prove that, "if the statement is true for any value up to a certain 'level', then it is also true for the next level"
    That is, if it is true for some n, then, you use this truth to prove that it is also true at n+1, and since you had a proof that it was true at 0, then 1 will follow, then 2, etc.

    3. this is the trickiest part of the proof, and I'm not too sure about what you really need to know, I think you should first make sure that the points 1. and 2. are well understood, let me know.

  6. Jun 22, 2012 #5
    Its starting to make sense.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook