# gcd proof 1

• January 21st 2010, 03:22 PM
Deepu
gcd proof 1
let a,b,c belongs to integers.prove that the equation ax+by=c has integer solutions if and only if (a,b)|c.
• January 21st 2010, 03:28 PM
Drexel28
Quote:

Originally Posted by Deepu
let a,b,c belongs to integers.prove that the equation ax+by=c has integer solutions if and only if (a,b)|c.

This is a number theory proof. If $ax+by=c$ then we have that $(a,b)\mid ax,by\implies (a,b)\mid ax+by=c$. Try the other way.
• January 21st 2010, 03:34 PM
Deepu
Quote:

Originally Posted by Drexel28
This is a number theory proof. If $ax+by=c$ then we have that $(a,b)\mid ax,by\implies (a,b)\mid ax+by=c$. Try the other way.

Thank you... but can you do this proof by the concept of division algorithm method..
• January 21st 2010, 03:38 PM
Drexel28
Quote:

Originally Posted by Deepu
Thank you... but can you do this proof by the concept of division algorithm method..

No. Can you?