- #1
BicycleTree
- 520
- 0
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.
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.