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 - The Fusion of Science and Community**

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

Loading...

Similar Threads - proof | Date |
---|---|

A Is the proof of these results correct? | Jan 29, 2018 |

I Doubt about proof on self-adjoint operators. | Nov 11, 2017 |

I Addition of exponents proof in group theory | Sep 2, 2017 |

B Help understanding a proof | Jun 8, 2017 |

**Physics Forums - The Fusion of Science and Community**