- #1
Miike012
- 1,009
- 0
Corollary from book:
if d= gcd(a,b), then there exists integers x and y such that ax + by = d.
This is not an obvious statement to me. Are there any direct proofs to prove this statement? The book proves this by induction.
My proof:
Suppose d = gcd(a,b) and a and b are positive integers. a does not necessarily divide b and b does not necessarily divide a so
let qa and ra be integers such that a = qab + ra. If d|a then d|(qab + ra) therefore d|ra, that is there exists an integer Ra such that ra = Rad.
Let qb and rb be integers such that b = qba + rb. We can see d|rb so Let Rb be the integer such that rb = Rbd.
now
a + b = qab + qba + (Ra + Rb)d and
a(1-qb)/(Ra + Rb) + b(1-qa)/(Ra + Rb) = d.
Now I just need to prove that the coef. of a and b are integers...
if d= gcd(a,b), then there exists integers x and y such that ax + by = d.
This is not an obvious statement to me. Are there any direct proofs to prove this statement? The book proves this by induction.
My proof:
Suppose d = gcd(a,b) and a and b are positive integers. a does not necessarily divide b and b does not necessarily divide a so
let qa and ra be integers such that a = qab + ra. If d|a then d|(qab + ra) therefore d|ra, that is there exists an integer Ra such that ra = Rad.
Let qb and rb be integers such that b = qba + rb. We can see d|rb so Let Rb be the integer such that rb = Rbd.
now
a + b = qab + qba + (Ra + Rb)d and
a(1-qb)/(Ra + Rb) + b(1-qa)/(Ra + Rb) = d.
Now I just need to prove that the coef. of a and b are integers...
Last edited: