# Euclidean algorithm and assumption of division algorithm

From university notes:

"In Euclidean we use the division alogorithm we assume that m | a and m | b iff m | b and m | r, considering a = qb + r, therefore (a,b) = (b,c)"

Can someone explain this assumption which is given for granted ?

-

I think you left out some of the context of the problem (e.g., what does $c$ refer to?), but the Euclidean division algorithm states that

For any integer $a$, given a positive integer $b$, we can be express $a$ in the form $\,a = qb + r,\;$ where $\,q\,$ and $\,r\,$ are unique integers, $0 \leq r \lt b$.

That is, when $a$ is divided by $b$, there is a unique quotient $q$ and a unique remainder $r$, $0 \leq r \lt b$.

E.g. (1) So for example, if $a = 21$ and $b = 4$, this can be expressed uniquely as $\,a = 5\cdot4 + 1$, where here, $q = 5$ and $r = 1$.

E.g. (2) If $a = -2,\;b = 3$, then $\,-2 = -1(3) + 1.$ That is, $q = -1$ and $r = 1$.

The negative numbers in example (2) seem counter-intuitive, but it ensures the existence of a unique integer $q$ and a unique integer $r: 0 \leq r \lt b$, given any integer $a$ and any positive integer divisor $b$, and it is in keeping with modular arithmetic:

$$a\equiv r \pmod b$$ where we express $r$ as a positive integer $0 \leq r \lt b$, and in this case $$-2 \equiv 1 \pmod 3$$

-

To show $\rm\, (a\!-\!qb,b) = (a,b)\:$ it suffices to show both pairs have equal sets $\rm\,D\,$ of common divisors, since then they have the same greatest common divisor $\rm (= max\ D).$ Thus we need to show

$$\rm d\mid a\!-\!qb,b\iff d\mid a,b$$

Proof $\rm\ \ (\Leftarrow)\ \ \ d\mid \color{#C00}{a,b}\ \Rightarrow\ d\mid \color{#C00}a\! -\! q\,\color{#C00}b,\ \ d\mid \color{#C00}b$

$\rm (\Rightarrow)\quad\quad\, d\mid \color{#C00}{a\!-\!qb,b}\ \Rightarrow\ d\mid \color{#C00} {a\! -\! qb} + q\color{#C00}b = a,\ \ d\mid \color{#C00}b$

Remark $\$ The proof uses only that the set of multiples of $\rm\,d\,$ are closed under addition, and also closed under multiplication by any integer (above, multiplication by $\rm\,q\in \Bbb Z).$ If you know modular arithmetic (congruences) then you may find more intuitive the following simple proof

$$\rm mod\ d\!:\ \ if\ \ \ \color{#C00}b\equiv 0\ \ \ then\ \ \ a-q\color{#C00}b\equiv 0\!\iff\! a\equiv 0$$

-

I take it you mean the assumption $$a=qb+r \quad and \quad 0\le r \lt|b|)$$ For simplicity I will prove it for $a \ge0, \quad b\gt0$

If $a\lt b$ we set $q=0, r=a$. Obviously $a=qb+r$ and $0\le r \lt b$

Now let $a\ge b$ and let $q$ be the biggest natural number such that $a\ge qb$ i.e. $$qb\le a\lt (q+1)b$$. Then $0\le r=a-qb\lt b$ and obviously $a=qb+r$

Now you can easily extend the proof to all integers. q.e.d.

p.s. You can show that $q,r$ are unique.

-

The fact that $\gcd(a,b)=\gcd(b,r)$ is easy to prove.

Let $d_1=\gcd(a,b)$; $d_2=\gcd(b,r)$. Then it is easy to show that $d_1 \mid d_2$ and $d_2 \mid d_1$. From here it follows that $d_1=d_2$.

To show that $d_1 \mid d_2$ you simply observe that since $d_1 \mid a$ and $d_1 \mid b$ we have $d_1 \mid a-qb=r$. Thus $d_1 \mid b$ and $d_1 \mid r$.

The other divisibility is similar....

-