How can the common divisor theorem be proven using proof by induction?

[hawaiifiver]

Hello

Can someone explain it to me sentence by sentence. Thank you. Here is the link

http://www.math.nus.edu.sg/~chanhh/MA4263/Chapter1.pdf

 

[oli4]

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

Cheers...

 

[hawaiifiver]

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.

Thanks

 

[oli4]

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.

Cheers...

 

[hawaiifiver]

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.

Cheers...

Its starting to make sense.