gcd(a,b) explanation using the set $\{ax+by : x,y \in \mathbb{Z}\}$

Question

I'm reviewing a proof of the greatest common divisor. The textbook describes $\gcd(a,b)$ as the smallest positive element in the set $\{ax+by : x,y \in \mathbb{Z}\}$. I'm not quite understanding this.

I tried to play with some numbers for example, $\gcd(55, 100)$ then plugging into the set:

$\{55x+100y : x,y \in \mathbb{Z}\}$. but not sure where to go from here or how this set helps me understand gcd.

Answer 1

The integers are ordered by "$\ge$"-relation. Your set $S:= \{ax+by : x,y \in \mathbb{Z}\}$ is a subset of integers, so it inherits this relation. You essentially looking for an element $g \in S$ with $g >0$ and such that for all $s \in S$ with $s>0$: $s \ge g$. The Euclidean algorith (https://en.wikipedia.org/wiki/Euclidean_algorithm) provides the method to calculate it. In your example it's $5$.

Answer 2

The ideal generated by two elements $(a,b)$ is principal (since $\mathbf Z$ is a P.I.D.) and it has two generators, with the same absolute value, and opposite signs. What is called the g.c.d. is the positive generator of this ideal, which can be obtained by the Euclidean algorithm. If $d=\gcd(a,b)$ we can write $d=ua+vb$ for some coefficients $u,v\in\mathbf Z$, and these coefficients can be explicitly obtained in all cases by the extended Euclidean algorithm, which relies on the observation that all remainders in the successive divisions of the Euclidean algorithm are linear combination of the two given numbers, up to the last one, which is the g.c.d. If we denote $r_i, q_i$ the remainder and quotient at the $i$-th step, and $u_i, v_i$ the coefficients of $r_i$ as a linear combination of $a$ and $b$, and coefficients can be calculated recursively.

Indeed, from the $i$-th division: $r_{i-1}=q_ir_i+r_{i+1}`\iff r_{i+1}=q_i r_i-r_{i-1}$, one deduces instantly the relations between the coefficient of $a$ and $b$: $$ u_{i+1}=q_iu_i-u_{i-1}, \qquad v_{i+1}=q_iv_i-v_{i-1}.$$ In the present case, it goes this way: \begin{array}{rrrl} r_i&u_i&v_i&q_i \\ \hline 100&0&1 \\ 55&1&0&1\\ \hline 45&-1&1&1\\ 10&2&-1&4\\ 5&\color{red}{-9}&\color{red}5 &2\\ \hline 0 \end{array} Indeed you can check that $\gcd(55,100)=5=-9\cdot 55+5\cdot 100$.