- #1
kntsy
- 80
- 0
urgent algebra GCD Proof problem
let d=gcd(m,n). Prove that d=am+bn, where a,b are integers.
use of induction and euclidean algorithm.
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.
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.