gcd proof 1

**Deepu** · January 21st 2010, 03:22 PM

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

**Drexel28** · January 21st 2010, 03:28 PM

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.

**Deepu** · January 21st 2010, 03:34 PM

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..

**Drexel28** · January 21st 2010, 03:38 PM

Originally Posted by Deepu

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

No. Can you?

Thread: gcd proof 1