Direct Proof of gcd(a,b) Corollary: ax+by=d

[Miike012]

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_a and r_a be integers such that a = q_ab + r_a. If d|a then d|(q_ab + r_a) therefore d|r_a, that is there exists an integer R_a such that r_a = R_ad.

Let q_b and r_b be integers such that b = q_ba + r_b. We can see d|r_b so Let R_b be the integer such that r_b = R_bd.

now
a + b = q_ab + q_ba + (R_a + R_b)d and
a(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...

 

[verty]

The extended Euclidean algorithm calculates those coefficients, so one avenue is an invariant-based proof based on that algorithm. Otherwise, a proof by contradiction should be doable.