I'm currently reading a book on discrete mathematics, more specifically I'm having a look at the chapter that covers some elementary number theory. There I read about something called Euclid's algorithm which can be used to find the greatest common divisior of two numbers. It was claimed that if this algorithm is used in reverse then it can be shown that
$\forall a,b\in \mathbb{Q}\enspace\exists x,y \in \mathbb{Z}:\operatorname{gcd}(a,b)=xa+yb$.
The proof of this was omitted and only a special case was demonstrated. I however am not entirely convinced that this theorem holds true just from observing a special case. I am unable to run the algorithm in reverse in my head in the case where the numbers are arbitrary.
Can anyone help me prove this theorem? How can I consider the aformentioned argument in order to be convinced that the theorem ought to be true?
Any help is appreciated.
DO you believe that the Euclidean algorithm itself works?
In my version of that algorithm, we say that $$ gcd(p, q) = gcd(p, q-p) $$ whenever $q \le p$, and when $q > p$, we change $$ gcd(p, q) = gcp(q, p) $$ so that we're back in the previous case. When we reach $$ gcd(p, 0) $$ the answer is $p$.
I claim that during this process, when used to compute $gcd(x, y)$, the arguments to "gcd" (the two numbers you're putting in there) are always of the form $ax + by$, where $a$ and $b$ are integers. I'll call such things "integer combinations of $x$ and $y$".
For the second case (swapping), this is easy: if $p$ and $q$ are integer combinations of $x$ and $y$, then $q$ and $p$ are integer combinations of $x$ and $y$. (For instance, if $p = 3x + 7y, q = 2x - 4y$, then $q = 2x - 4y, p = 3x + 7y$; it's that simple!)
For the first case, suppose that $p $ and $q$ are both integer combinations, say $$ p = ax + by \\ q = cx + dy $$ Then after we apply the transformation, we have two NEW arguments, $p$ and $q-p$. Are these both integer combinations of $x$ and $y$? Yes. For $$ p = ax + by \\ q-p = (cx + dy) - (ax + by) = (c-a)x + (d-b)y $$
So if you start with $x$ and $y$ and apply the euclidean algorithm, the number-pairs that show up in gcd will always be integer combinations, because the FIRST number pair, $x$ and $y$ are: $$ x = 1 \cdot x + 0 \cdot y\\ y = 0 \cdot x + 1 \cdot y $$ and hence the next pair is, and the next pair, and so on. (I'm hiding an induction argument here, but I hope I'm convincing you anyhow).
Well, at the very last step, you have $$ gcd(s, 0) $$ for some $s$. And hence $s$ (which is the gcd you're looking for) must be an integer combination of $x$ and $y$.
==== So that's a proof of the claim, at least for the case where $a$ and $b$ are integers. For the case where $a$ and $b$ are rational, as you've written...I don't think that quite makes sense. The greatest common divisor of a pair of rationals is not usually defined. But if you tell me the definition that the book uses, I'll happily try to flesh out this argument to cover that case.