(adsbygoogle = window.adsbygoogle || []).push({}); Theorem:

For all a,b,c E Z such that a and b are not both 0,

there exist x,y E Z such that ax+by=c <=> gcd(a,b)|c.

Here is my attempt of proving it...

(<=) Sppose gcd(a,b)|c

By theorem, there exists k,m E Z such that gcd(a,b) = ka+mb

Now gcd(a,b)|c => gcd(a,b)=c/s for some s E Z.

=> c/s = ka+mb => c=(ks)a+ (ms)b with (ks) and (ms) integers.

But I have some trouble proving the converse of this.

(=>) Suppose there exist x,y E Z such that ax+by=c.

By theorem, there exists k,m E Z such that gcd(a,b) = ka+mb

Now I need to prove that gcd(a,b)|c, i.e. c = r gcd(a,b) for some r E Z. How can we prove this? I really have no idea at this point...

Can someone please help me?

**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!

# Ax+by=c => gcd(a,b)|c ?

Loading...

Similar Threads for Ax+by=c | Date |
---|---|

A Why a Lie Group is closed in GL(n,C)? | Feb 12, 2018 |

I Groups of Automorphisms - Aut(C) ... | Jul 2, 2017 |

I Linear dependency of Vectors above R and C and the det | May 21, 2016 |

How to find basis vectors for a+ ax^2+bx^4? | Feb 17, 2016 |

Jordan Chains to solve x'=Ax, complex-valued. | Feb 8, 2016 |

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