# Gcd proof

1. May 25, 2005

### 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.

2. May 25, 2005

### Hurkyl

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

3. May 26, 2005

### 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.

4. May 26, 2005

### snoble

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.

5. May 26, 2005

### 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.

6. May 26, 2005

### 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.

7. May 26, 2005

### 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.

8. May 26, 2005

### Hurkyl

Staff Emeritus
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.

9. May 26, 2005

### 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.

10. May 27, 2005

### snoble

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

11. May 27, 2005

### Hurkyl

Staff Emeritus
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)

12. May 27, 2005

### BicycleTree

I see. That is very simple.