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

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

Know someone interested in this topic? Share a link to this question via email,
Google+,
Twitter, or
Facebook

Have something to add?

- Similar discussions for: Ax+by=c => gcd(a,b)|c ?

Loading...

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