proof by contradiction that GCD( a, b) is a linear combination of a and b

Question

Lets says z is GCD of A and B then it is intutive that z has to divide any linear combination of A and B => z | ( Ax + By ) therefore we know z <= ( Ax + By ) but how can we proove by contradiction that for a value of x and y we can write z = Ax + By ?

Answer 1

By contradiction? Here's your proof, but we'll start with relatively prime numbers $A$ and $B$.

Suppose $d$ is the smallest number that is expressible as $Ax+By$, and suppose that $d>1$. Now, $d$ can't divide both $A$ and $B$, because it is greater than their gcd.

Without loss of generality, $d$ does not divide $A$. By the Euclidean algorithm, write $A=dq+r$, where $0<r<d$.

Now, $$ r=A-dq = A-(Ax+By)q = A(1-qx) + B(-qy) $$

contradicting that $d$ was the smallest such number. Thus, $d \leq 1$. But then, $d=1$,by the fact that every non-empty set of natural numbers has a smallest number. So it follows that $Ax+By=1$ for some $x$ and $y$.

It's not very difficult to generalize this. Note that if $gcd(A,B)=z$, then $gcd(A/z,B/z)=1$, so there are $x$ and $y$ such that $Ax/z+By/z=1 \implies Ax+By=z$.Now, use a similar logic to above to show Bezout's identity in general.