2
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ en.wikipedia.org/wiki/Extended_Euclidean_algorithm $\endgroup$ – Lord Shark the Unknown Sep 24 '17 at 11:35
  • $\begingroup$ $G:=\{\,xa+yb\mid x,y\in\Bbb Z\,\}$ is a discrete subgroup of $\Bbb Q$, hence eithre trivial (iff $a=b=0$) or has a minimal positive element $d$, for which we then have $G=\langle d\rangle$. Then from $a,b\in G$, we get $d\mid a$ and $d\mid b$. $\endgroup$ – Hagen von Eitzen Sep 24 '17 at 11:37
  • 1
    $\begingroup$ Are you sure the claim specifies rational numbers $a$ and $b$, not integers? $\endgroup$ – Ethan Bolker Sep 24 '17 at 12:08
2
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Thank you very much! The book did not say that $a$ and $b$ had to be rational, I just messed up. The authors claimed that they were integers as well. I greatly appreciate that you took the time to write all of this down. $\endgroup$ – David Sep 24 '17 at 14:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.