Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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 ?

share|cite|improve this question
up vote 3 down vote accepted

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

share|cite|improve this answer

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

share|cite|improve this answer

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.

share|cite|improve this answer

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

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.