Proving the GCD Property: A Challenge for Algebra Students

[kntsy]

urgent algebra GCD Proof problem

Homework Statement

let d=gcd(m,n). Prove that d=am+bn, where a,b are integers.

Homework Equations

use of induction and euclidean algorithm.

The Attempt at a Solution

i know when d being a generator and d=am+bn where m,n are generators, then d=gcd(m,n).
But i got stuck when proving the converse(which is the problem statement above).

I use the iterative algorithm(i.e. "n=qm+r";gcd(m,n)=gcd(m,r) and so on) but just does not work. And i do not know how to use "induction" in this proof.

Thank you for helping me.

 

[VeeEight]

Use the Euclidean algorithm.