For a, b, c, d positive integers, and d = a + bc, prove that gcd(b, d) = gcd(a, b).(adsbygoogle = window.adsbygoogle || []).push({});

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.

**Physics Forums | Science Articles, Homework Help, Discussion**

Dismiss Notice

Join Physics Forums Today!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# Gcd proof

**Physics Forums | Science Articles, Homework Help, Discussion**