# Discrete math (gcd)

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

## Answers and Replies

Homework Helper
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.