Prove: GCD of a, b and d is Equal to GCD of a and b

[BicycleTree]

For a, b, c, d positive integers, and d = a + bc, prove that gcd(b, d) = gcd(a, b).

I don't know about this. I can use the definition of gcd, the diophantine equation of the form as + bt = c and how it relates to the gcd, and the division algorithm theorem.

I know that gcd(a, b) divides d and gcd(b, d) divides a. I might try to show that gcd(a, b) = gcd(a + b, b) for c = 1 and then use induction for other values of c. But I don't know how to prove the base case.

 

[Hurkyl]

The "diophantine" version is most often the most useful method for proof.

 

[johnnyICON]

What is the diophantine version? My professor mentioned it yesterday in class but he never formerly stated it. I feel like I'm missing so many important details.

 

[snoble]

I know that gcd(a, b) divides d and gcd(b, d) divides a.

This seems to me to be all you really need. You know that gcd(a,b) divides d and a and b, same for gcd(b,d). Then there's a straight forward contradiction why gcd(a,b) can't be greater than gcd(b,d) and vice versa.

 

[BicycleTree]

Well, I did figure it out one way. gcd(a, b) = gcd(a + b, b) because gcd(a, b) | a and b therefore gcd(a, b) | a + b and b, and if x | a + b and x | b then x | a (x | a is what I was missing before) so x | a and x | b so by the definition of gcd, x | gcd(a, b). So gcd(a, b) = gcd(a + b, b), or gcd(a , b) = gcd(a + 1b, b).

Then using induction, assume gcd(a, b) = gcd(a + b(c-1), b). Then since gcd(a + b(c-1), b) = gcd(a + b(c-1) + b, b) = gcd(a + bc, b), gcd(a, b) = gcd(a + bc, b) for all positive integers c. Since d = a + bc, gcd(a, b) = gcd(b, d).

Snoble, I see. If gcd(a, b) > gcd(b, d) then gcd(b, d) does not divide gcd(a, b) (since they are positive) yet gcd(a, b) divides b and d, contradicting the definition of gcd, and the other way around.

 

[snoble]

All I meant was that if gcd(a,b) > gcd(b,d) then gcd(a,b) is a common denominator of b and d that seems to greater than the greatest common denominator.

 

[BicycleTree]

I said that (paragraph 3). My book defined gcd in terms of "divides" rather than actually "greater than"; gcd(a, b) is the positive number x so that x | a and x | b, and for any y that divides a and b, y | x, so I have to translate.

 

[Hurkyl]

I presume by "diophantine version" he means that the gcd(x, y) is the smallest positive integer of the form px + qy. (With p and q both integers)

This problem is utterly trivial with this characterization.

 

[BicycleTree]

Well, that diophantine equation was how I learned that gcd(a, b) | d and gcd(b, d) | a. Can it be done more easily than that?

My post #5 of this thread contained two different proofs--one in paragraphs 1 and 2 and the other in paragraph 3 based on snoble's suggestion.

 

[snoble]

I said that (paragraph 3). My book defined gcd in terms of "divides" rather than actually "greater than"; gcd(a, b) is the positive number x so that x | a and x | b, and for any y that divides a and b, y | x, so I have to translate.

Oh sorry. Your definition is definitely the better definition since it is much more general... I should probably try to use it myself more often

Thanks,
Steven

 

[Hurkyl]

Applying the definition, the original question asks you to prove:


The smallest positive number of the form:

ap + bq

is equal to the smallest positive number of the form:

by + (a + bc)z = az + b(y+cz)

 

[BicycleTree]

Applying the definition, the original question asks you to prove:


The smallest positive number of the form:

ap + bq

is equal to the smallest positive number of the form:

by + (a + bc)z = az + b(y+cz)

I see. That is very simple.