Multiples are closed under integral linear combinations

Question

My lecturer gave us the following side note when explaining the euclidean algorithm in class.

Eucledian Algorithm: Let $a$ and $b$ be natural numbers, then there are integers $m$ and $n$ such that $\gcd(a, b) = am + bn$

The implementation of the Euclidean Algorithm consists of a sequence of repetitions of the Division Algorithm with the integers m and n being obtained by unravelling this sequence of steps. To appreciate why such an operation identifies $\gcd(a, b)$, we may start with the assumption that $a > b$ otherwise $\gcd(a, b) = a$ (the case $a = b$) and there is nothing to be done. When $a > b$ the Division Algorithm asserts that $a = bq + r$ with $0 r < b.$ There are two points to note. a) Since $\gcd(a, b)$ divides $a$ and $b$ so $\gcd(a, b)$ must also divide the remainder $r.$ Therefore the greatest common divisor of $a$ and $b$ is also the greatest common divisor of $b$ and $r$, that is, $\gcd(a, b) = \gcd(b, r)$. b) Since $b < a$ and $r < b$ the sequence of applications of the Division Algorithm generates a strictly decreasing sequence of remainders terminating with 0, but such that each remainder is divisible by $\gcd(b, r)$. By definition, the penultimate remainder is therefore $\gcd(a, b)$.

I understand and can apply the algorithm, i.e. I can do the repeated division and find the gcd. But I still don't understand the part in bold above. Why can we just assume that?

When trying to prove the same for polynomials in a tutorial homework, I simply used a modified version of the part in bold as a lemma, specifically:

Any polynomial divisor of both $f(x)$ and $g(x)$ must also divide the remainder polynomial when $f(x)$ is divided by $g(x)$

and the tutor made no remark, so I'm assuming this is something which can be clearly seen but that I'm missing. Could anyone please break it down for me?

Answer 1

Let $d=\gcd(a,b)$. You know $d$ divides both $a$ and $b$, and that means there are integers $k,l\in\mathbb{Z}$ such that $a=dk,b=dl$. And hence:

$r=a-bq=dk-dlq=d(k-lq)$

When $k-lq\in\mathbb{Z}$. So we got $d$ divides $r$.

Answer 2

Well, if $d$ is the gcd of $a$ and $b$, and $a = qb+r$ where $r$ is the remainder, then $r= a - qb$. Thus $d$ divides the right-hand side and so $r$.

Answer 3

They are both the same:

If you ever have $k\mid M$ and $k\mid N$ then you have $k|aM \pm bN$ for any integers $a,b$.

Pf: Do we really have to prove it? $x\mid W \iff \frac Wx \in \mathbb Z$. So $\frac {aM \pm bN}k = a\frac Mk \pm b\frac Nk$. $k\mid M$ and $k\mid N$ so $\frac Mk, \frac NK$ are integers. So $\frac {aM \pm bN}k = > a\frac Mk \pm b\frac Nk$ is an integer. So $k|aM \pm bN$.

So $a = bq + r$ so $r = a - bq$ and $\gcd(a,b)|a$ and $\gcd(a,b)\mid b$ so $\gcd(a,b)\mid a - bq = r$.

That's it.

And for polynomials.

$f(x) = g(x)q(x) + r(x)$ then $r(x) = g(x)q(x) - f(x) = d(x) \left [\frac {g(x)}{d(x)} q(x) - \frac {f(x)}{d(x)} \right]$

Answer 4

Key Idea $ $ Sets of $\rm\color{#c00}{integer}$ multiples (of $\,d)$ enjoy a fundamental linear structure - namely they are closed under $\rm\color{#c00}{integral}$ linear combinations, i.e.

$\ \ $ if $\,\ \begin{align}a = \color{#c00}j\,d\\ b = \color{#c00}k\,d\end{align}\ \,$ are multiples of $\,d\,$ then so too is $\,ma\!+\!nb = \color{#c00}{(mj\!+\!nk)}d,\ $ for all integers $\,\color{#c00}{m,n}$

$ r = a\color{#c00}{-q}\,b\,$ is an $\rm\color{#c00}{integral}$ linear combination of multiples $\,a,b\,$ of $\,d\,$ so it too is a multiple of $\,d$.

Example $ $ If $\,ma+nb = 1\,$ then every common divisor of $a,b$ also divides $1,$ so $\,a,b\,$ are coprime.

The same is true for multiples in any ring $R\,$ if we replace the $\rm\color{#c00}{integral}$ multipliers $\,\color{#c00}{m,n}\,$ by arbitrary ring elements (e.g. polynomials in your second case), i.e. we use $R$-linear combinations.

This linear algebraic structure persists for multiples of many elements ("common multiples"). It is a prototypical example of an ideal $(R$-module) - a ubiquitous structure in number theory and algebra, so it is helpful to be familiar with this fundamental linear structure early in one's studies.

---

Alternatively: $\,\ d\mid a,b\Rightarrow (ja\!+\!kb\bmod d)= 0\!+\!0\,$ so $\,d\mid ja\!+\!kb\,$ by divisibility mod reduction. By congruences: $ 0\equiv a,b\Rightarrow\, ja\!+\!kb\equiv j(0)\!+\!k(0)\equiv 0\pmod{\!d}\,$ by congruence sum & product rules.