Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Algebra GCD Proof problem

  1. Sep 21, 2010 #1
    urgent algebra GCD Proof problem

    1. The problem statement, all variables and given/known data
    let d=gcd(m,n). Prove that d=am+bn, where a,b are integers.


    2. Relevant equations
    use of induction and euclidean algorithm.


    3. 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.
     
  2. jcsd
  3. Sep 21, 2010 #2
    Re: urgent algebra GCD Proof problem

    Use the Euclidean algorithm.
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook