Why $\gcd(b,qb+r)=\gcd(b,r),\,$ so $\,\gcd(b,a) = \gcd(b,a\bmod b)$

Given: $a = qb + r$. Then it holds that $\gcd(a,b)=\gcd(b,r)$. That doesn't sound logical to me. Why is this so?

Addendum by LePressentiment on 11/29/2013: (in the interest of http://meta.math.stackexchange.com/a/4110/53259 and averting a duplicate)

What's the intuition behind this result? I only recognise the proof and examples solely due to algebraic properties and formal definitions; I'd like to apprehend the result naturally.

Solution 1:

Hint $ $ note if $\rm\, d\mid \color{#c00}b\ $ then $\rm\ d\,\mid\, q \color{#c00}b + r \!\iff d\ |\ r, \ $ i.e. arithmetically in congruence language:
$\!\rm\bmod d^{\phantom{|^|}}\!\!\!\!:\ $ if $\rm\ \color{#c00}{b\equiv 0}\ $ then $\rm\ q\color{#c00}b+r\equiv 0 \!\iff\! r\equiv 0\ $ by congruence sum & product rules.

By above $\rm\, \{qb+r,b\}\, $ and $\rm\, \{r,\, b\}\, $ have the same set $\,\rm S\,$ of common divisors $\rm\,d,\,$ which implies that they also have the same greatest common divisor $\rm(= \max S)$.

Thus $\rm \,\bbox[5px,border:1px solid #c00]{\gcd(a,b) = \gcd(r,b)\,\ {\rm if}\,\ a\equiv r\pmod{\! b}} \,$ since then $\rm\, a = qb+r\,$ for $\,r\in\Bbb Z$

e.g. $\ \ \rm \bbox[5px,border:1px solid #c00]{\gcd(a,b) = \gcd(a\bmod b,b)}\,\ $ by choosing $\rm \, r = a\bmod b,\, $ using the division algorithm. $ $ This gcd modular reduction is the descent (induction) step in the well-known classical recursive Euclidean algorithm for the gcd.

Also $\rm\, d\mid a\iff d\mid r\ $ if $\rm \ a\equiv r\pmod{\! d},\,$ since then $\rm\,a = qd+r\,$ so the above applies.
So $\ \ \,\rm \bbox[5px,border:1px solid #c00]{\!d\mid a\iff d\mid (a\bmod d)}.\,$ This divisibility mod reduction often simplifies matters.

Generally the set of multiples of $\rm\,d\,$ are closed under integral linear combinations, and ditto for common multiples of any set of integers, which leads to the universal property of the lcm, using descent via the Euclidean division algorithm.

Remark $ $ The result holds true because $\rm\,\mathbb Z\,$ forms a subring of its fraction field $\rm\,\mathbb Q.\,$ More generally, given any subring $\rm\,Z\,$ of a field $\rm\,F\,$ we define divisibility relative to $\rm\ Z\ $ by $\rm\ x\mid y \iff y/x\in Z.\,$ The above proof still works, since if $\rm\ q,\ b/d\ \in Z\, $ then $\rm\, q\,(b/d) + r/d\in Z\iff r/d\in Z.\,$ Thus the common divisibility laws follow from the fact that (sub)rings are closed under subtraction and multiplication (subring test). Being so closed, $\rm\,Z\,$ serves as a ring of "integers" for divisibility tests.

For example, to focus on the prime $2$ we can ignore all odd primes and define a divisibility relation so that $\rm\ m\ |\ n\ $ if the power of $2$ in $\rm\,m\,$ is $\le$ that in $\rm\,n\,$ or, equivalently if $\rm\ n/m\ $ has odd denominator in lowest terms. The set of all such fractions forms a ring $\rm\,Z\,$ of $2$-integral fractions. Moreover, this ring enjoys parity, so arguments based upon even/odd arithmetic go through. Similar ideas lead to powerful local-global techniques of reducing divisibility problems from complicated "global" rings to simpler "local" rings, where divisibility is decided by simply comparing powers of a prime.

Solution 2:

If $d$ is a divisor of $a$ and of $b$, then $$ \begin{align} a & = dn, \\ b & = dm. \end{align} $$ So $$a-b= dn-dm=d(n-m)= (d\cdot\text{something}).$$ So $d$ is a divisor of $a-b$.

Thus: All divisors that $a$ and $b$ have in common are divisors of $a-b$.

If $d$ is a divisor of $a$ and of $a-b$, then $$ \begin{align} a & = dn, \\ a-b & = d\ell. \end{align} $$ So $$ b=a-(a-b)=dn-d\ell=(d\cdot\text{something}). $$ So $d$ is a divisor of $b$.

Thus: All divisors that $a$ and $a-b$ have in common are divisors of $b$.

Therefore, the set of all common divisors of $a$ and $b$ is the same as the set of all common divisors of $a$ and $a-b$.

Subtracting one member of a pair from the other never alters the set of all common divisors; therefore it never alters the $\gcd$.

Solution 3:

You can show that for any integer $d$, we have $d\; |\; a$ and $d\; |\; b$ if and only if $d\; |\; b$ and $d\; |\; r$. In other words, $a$ and $b$ have exactly the same common divisors as $b$ and $r$. Thus $\gcd(a,b)$ is the same as $\gcd(b,r)$.

Solution 4:

Since set of common divisors of $a-b$ and $b$ coincides with the set of common divisors of $a$ and $b$ then $\operatorname{gcd}(a,b)=\operatorname{gcd}(a-b,b)$. If $a=qb+r$, where $b>0$ and $0\leq r<b$, you can apply this equality $q$ times and obtain $\operatorname{gcd}(a,b)=\operatorname{gcd}(r,b)$