Proof:
First, consider the set of . Since consists of non-negative integers there exists a minimal element . So . Then by the division algorithm , . This means that is a linear combination of . If then but this contradicts the minimality of so . Hence . The same argument can be made to show that meaning . Since and , so we get and so
Remark
This also proves that as was the minimal element.
You can figure out and by going through the Euclidean Algorithm backwards and collecting like terms.
Two integers , are coprime if so by Bezout’s Identity s.t