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 ?
 A: 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$$ 
A: 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.
A: 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.... 
A: 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$$
