Greatest common divisor of a and b

[mathmari]

Hey!

The greatest common divisor of $a$ and $b$ can be written as a linear combination of $a$ and $b$.
Let the set $D=\{xa+yb|x,y \in Z\}$.

a) $D$ contains non-zero elements.

b) $D$ contains also positive numbers.

c) The set of positive numbers of $D$ (let $D^+$) is $ \neq \varnothing$, so it has a minimum element. Let $d$ be the minimum element of $D^+ \subset D$
Consider that $d$ is the GCD of $a$,$b$.
First of all, since $d \in D$, $\exists x_1, y_1 \in Z$ so that $d=x_1 a+ y_1 b$
Consider that each element of $D$ is a multiple of $d$ and each multiple of $d$ belongs to $D$, so let's consider that $\{ax+by|x,y \in Z\}=D=dZ$

I haven't understood why we consider at c) that $d$ is the GCD of $a$,$b$. Could you explain it to me??

 

[I like Serena]

Hey!

The greatest common divisor of $a$ and $b$ can be written as a linear combination of $a$ and $b$.
Let the set $D=\{xa+yb|x,y \in Z\}$.

a) $D$ contains non-zero elements.

b) $D$ contains also positive numbers.

c) The set of positive numbers of $D$ (let $D^+$) is $ \neq \varnothing$, so it has a minimum element. Let $d$ be the minimum element of $D^+ \subset D$
Consider that $d$ is the GCD of $a$,$b$.
First of all, since $d \in D$, $\exists x_1, y_1 \in Z$ so that $d=x_1 a+ y_1 b$
Consider that each element of $D$ is a multiple of $d$ and each multiple of $d$ belongs to $D$, so let's consider that $\{ax+by|x,y \in Z\}=D=dZ$

I haven't understood why we consider at c) that $d$ is the GCD of $a$,$b$. Could you explain it to me??

Hi! :)

It's a consequence of the Euclidian algorithm, which is the algorithm to find the greatest common denominator.
It says that the smallest linear combination of 2 numbers is their greatest common denominator.

 

[Evgeny.Makarov]

It's a consequence of the Euclidian algorithm, which is the algorithm to find the greatest common denominator.
It says that the smallest linear combination of 2 numbers is their greatest common denominator.

I am sure all these facts are related, but I don't immediately see how to use the Euclidean algorithm to show that the smallest linear combination is the GCD. I see how to use the Euclidean algorithm to show that the GCD is a linear combination of the original numbers.

Concerning the OP's question, let $d=xa+yb$ be the smallest positive linear combination of $a$ and $b$. If $a=qd+r$ with $0<r<d$, then
\[
r=a-qd=a-q(xa+yb)= (1-qx)a-(qy)b
\]
is an even smaller positive linear combination. Thus, $d\mid a$ and similarly $d\mid b$. On the other hand, every linear combination of $a$ and $b$, including $d$, is divisible by any common divisor of $a$ and $b$.

 

[mathmari]

I am sure all these facts are related, but I don't immediately see how to use the Euclidean algorithm to show that the smallest linear combination is the GCD. I see how to use the Euclidean algorithm to show that the GCD is a linear combination of the original numbers.

Is it maybe like that:
From the Euclidean algorithm we have
$$b=q_1 a+r_1, 0 \leq r_1 < a$$
$$a=q_2 r_1 +r_2, 0 \leq r_2 <r_1$$
$$r_1 =q_3 r_2 + r_3, 0 \leq r_3 <r_2$$
$$...$$
$$r_{n-2}=q_n r_{n-1}+r_n, 0 \leq r_n <r_{n-1}$$
$$r_{n-1}=q_{n+1} r_n$$
The GCD is the last non-zero remainder, that is smaller that all the other remainders ($r_n<r_{n-1}<...$). So the smallest linear combination is the GCD.

 

[Evgeny.Makarov]

The GCD is the last non-zero remainder, that is smaller that all the other remainders ($r_n<r_{n-1}<...$). So the smallest linear combination is the GCD.

The smallest linear combination out of the set of all linear combinations or out of the set of combinations that appear in the algorithm? Post #1 talks about the smallest linear combination without any restrictions.

 

[Deveno]

There are 3 "definitions" of gcd(a,b) floating around here:

Definition #1:

$\text{gcd}(a,b) = \max(\{d \in \Bbb Z^+: d|a \text{ and } d|b\})$

Definition #2:

$\text{gcd}(a,b) = d \in \Bbb Z^+: c|a \text{ and } c|b \implies c|d$

Definition #3:

$\text{gcd}(a,b) = \min(\{ra + sb \in \Bbb Z^+: r,s \in \Bbb Z\})$.

So it would be nice to know that all of these definitions are EQUIVALENT (so we can use whichever one SUITS us).

Let's show that this is indeed so.

3 $\iff$ 1:

Let's (following the lead of the OP) call the set referenced in definition 3, $D^+$. First of all, we need to show $D^+$ is non-empty, but this is easy: Clearly $a \in D^+$ (and so is $b$).

Second, if we call the set referenced in definition 1, $M$, we need to show $M$ is non-empty, and also bounded above. It is clearly non-empty, because 1 is always in $M$, and it is bounded above by $\min(|a|,|b|)$.

Now every element of $M$ divides every element of $D^+$ since every element of $M$ is a common divisor of $a,b$. So if $m = \max(M)$, and $d = \min(D^+)$, we have: $m|d$, so $m \leq d$.

As Evgeny showed in his first post, we have $d|a$ and $d|b$, that is: $d \in M$. Thus:

$d \leq m \leq d$, so we have $m = d$.

3 $\implies$ 2:

Since $\text{gcd}(a,b) = \max(D^+) = d$, we have that any element of $M$ (as above) divides $d$. If $c$ is any common divisor of $a,b$ then $|c| \in M$, whence $|c|$ divides $d$, and thus either:

$d = ct$ (if $c = |c|)$ or:

$d = |c|t = (-c)t$ (if $|c| = -c$) so that in all cases $c|d$.

2 $\implies$ 1:

If $d$ is a common divisor with the property in (2), then $d \geq |c|$ for any other common divisor $c$, since $c|d$. Since $d \in M$, and is greater than or equal to every other member of $M$, it is the maximal member of $M$, which is what (1) states.

 

[I like Serena]

Is it maybe like that:
From the Euclidean algorithm we have
$$b=q_1 a+r_1, 0 \leq r_1 < a$$
$$a=q_2 r_1 +r_2, 0 \leq r_2 <r_1$$
$$r_1 =q_3 r_2 + r_3, 0 \leq r_3 <r_2$$
$$...$$
$$r_{n-2}=q_n r_{n-1}+r_n, 0 \leq r_n <r_{n-1}$$
$$r_{n-1}=q_{n+1} r_n$$
The GCD is the last non-zero remainder, that is smaller that all the other remainders ($r_n<r_{n-1}<...$). So the smallest linear combination is the GCD.

Sounds good to me! ;)

The smallest linear combination out of the set of all linear combinations or out of the set of combinations that appear in the algorithm? Post #1 talks about the smallest linear combination without any restrictions.

The algorithm is designed in such a way that it finds a smallest non-zero linear combination (the GCD). It effectively also gives you the class of all linear combinations that come out as the GCD. So those two are the same.

 

[Deveno]

Sounds good to me! ;)
The algorithm is designed in such a way that it finds a smallest non-zero linear combination (the GCD). It effectively also gives you the class of all linear combinations that come out as the GCD. So those two are the same.

It doesn't give you ALL linear combinations.

Ok, consider this:

gcd(3,5) = 1.

Using the Euclidean algorithm, we find that:

5 = 1(3) + 2
3 = 1(2) + 1
2 = 2(1) + 0

so:

1 = 3 - 1(2) = 3 - 1(5 - 1(3)) = 3 + (-1)(5) + (1)(3) = (1 + 1)(3) + (-1)(5) = 2(3) + (-1)(5).

In other words, the linear combination we get is:

(2)(3) + (-1)(5).

And indeed that equals the gcd. However, we have (for example) ANOTHER linear combination:

(12)(3) + (-7)(5) = 1.

I fail to see how this linear combination is produced from the Euclidean algorithm, as the quotient and remainder at each step is uniquely determined in that algorithm.

In short: the Euclidean algorithm is a good WAY to compute the gcd, but it is not a definition, per se, as it has to be PROVEN that the linear combination (which is only one out of many possible) so produced is indeed minimal.

This is not hard to do: for example one can show that, for b < a:

gcd(a,b) = gcd(a - b,b) = gcd(a - qb,b) = gcd(r,b).

By showing (for example) the gcd on each side of an equality divides the other, and using definition #2.

 

[I like Serena]

gcd(3,5) = 1.

In other words, the linear combination we get is:

(2)(3) + (-1)(5).

And indeed that equals the gcd. However, we have (for example) ANOTHER linear combination:

(12)(3) + (-7)(5) = 1.

I fail to see how this linear combination is produced from the Euclidean algorithm, as the quotient and remainder at each step is uniquely determined in that algorithm.

Note that $5\cdot 3 - 3 \cdot 5 = 0$.
This is the smallest non-zero linear combination that comes out as zero.
Add that twice to the first linear combination and you find the second linear combination.