Multiples are closed under integral linear combinations

Solution 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$.

Solution 2:

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$.

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.

Solution 3:

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$.

Solution 4:

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]$