- #1

- 1,011

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

Let q

now

a + b = q

a(1-q

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 q

_{a}and r_{a}be integers such that a = q_{a}b + r_{a}. If d|a then d|(q_{a}b + r_{a}) therefore d|r_{a}, that is there exists an integer R_{a}such that r_{a}= R_{a}d.Let q

_{b}and r_{b}be integers such that b = q_{b}a + r_{b}. We can see d|r_{b}so Let R_{b}be the integer such that r_{b}= R_{b}d.now

a + b = q

_{a}b + q_{b}a + (R_{a}+ R_{b})d anda(1-q

_{b})/(R_{a}+ R_{b}) + b(1-q_{a})/(R_{a}+ R_{b}) = d.Now I just need to prove that the coef. of a and b are integers...

Last edited: