# Why $\gcd(qb+r,b)=\gcd(b,r)$?

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.

• $a$, $b$, $r$ are integers? (If yes, tagging the question elementary-number-theory would be suitable.) Or are you looking for some greater generality, e.g. they are elements of some type of commutative ring? If yes, you should say so and you should also mention, what are the assumptions about this ring. – Martin Sleziak Jan 2 '12 at 13:12
• If you're asking about integers, then this question is very similar to yours: math.stackexchange.com/questions/59147/… – Martin Sleziak Jan 2 '12 at 13:16
• see page 13 here www-groups.dcs.st-and.ac.uk/~martyn/teaching/1003/… – Bhargav Jan 2 '12 at 13:26
• @Martin The result does not depend upon the underlying ring (assuming $\rm\:gcd(a,b)\:$ exists). – Bill Dubuque Jan 2 '12 at 18:19
• @BillDubuque I think that it would be better to close as a duplicate in the opposite direction (706016 $\to$ 95799 rather than 95799 $\to$ 706016). I think that the post which is the most useful should be left open, as discussed on meta. And this question has more answers and some answers are more detailed. I have also mentioned this in chat. – Martin Sleziak Jun 30 '16 at 6:41

Hint $$\rm\$$ If $$\rm\ \color{#c00}{d\ |\ b}\$$ then $$\rm\ d\ |\ q \color{#c00}b + r \iff d\ |\ r.\$$ Therefore $$\rm\ \{b,\:qb+r\}\$$ and $$\rm\ \{b,\: r\}\$$ have the same set $$\,\rm S\,$$ of common divisors $$\rm\:d,\:$$ so they have the same greatest common divisor $$\rm(= \max S)$$.

Said $$\rm\bmod d\!\!:\$$ if $$\rm\ \color{#c00}{b\equiv 0}\$$ then $$\rm\ q\color{#c00}b+r\equiv 0 \iff r\equiv 0$$

Note $$\$$ 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\ |\ y\ \iff\ y/x\in Z\:.\:$$ Then 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\:.\:$$ In other words, the usual divisibility laws follow from the fact that rings are closed under the operations of subtraction and multiplication; 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.

• Thank you! Extremely clear explanation :) – www.data-blogger.com Mar 26 '18 at 8:03

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

• Very clear answer! Little remark: $a-b \neq r$, but $a-qb = r$, but all your explanation will work using that :). – www.data-blogger.com Jan 2 '12 at 21:17
• @Kevin Beware that this fails if the ring is not $\rm\:\mathbb Z\:$ since then the remainder $\rm\:r\:$ generally cannot be obtained by repeatedly subtracting $\rm\:b\:$ from $\rm\ q\ b + r\:,\:$ as it can when $\rm\:q\in\mathbb N\:.\:$ In other words, in general Euclidean rings, e.g. the polynomial ring $\rm\:F[x]\:$ over a field $\rm\:F\:,\:$ the Euclidean algorithm generally requires division with remainder, not simply iterated subtraction, in order to effect descent to a "smaller" remainder. So this ad-hoc special-case doesn't generally reveal the essence of the matter. – Bill Dubuque Jan 2 '12 at 22:37
• @Kevin : Thanks; I've fixed the typo. – Michael Hardy Jan 3 '12 at 0:52
• To express Bill Dubuque's point in other way: Euclid's algorithm works for polynomials, but the argument I give in my answer doesn't work for polynomials unless you do some adaptations. – Michael Hardy Jan 3 '12 at 0:53
• The top comment is important - this answer, although clear, seems to be answering a different question. I'd like to see a similar explanation that involves the remainder rather than just subtraction. – Robin May 4 '17 at 9:45

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

• excellent answer, +1 for it. – ncmathsadist Jan 2 '12 at 13:44
• Thanks, but why do they have the same common divisors? – www.data-blogger.com Jan 2 '12 at 21:15
• @Kevin: If $d$ divides $a$ and $b$, then $d$ divides $-qb$ and thus divides the sum $a - qb = r$. This shows that any common divisor of $a$ and $b$ is a common divisor of $b$ and $r$. If $d$ divides $b$ and $r$, then $d$ divides $qb$ and thus divides the sum $qb + r$. This shows that any common divisor of $b$ and $r$ is a common divisor of $a$ and $b$. – Mikko Korhonen Jan 2 '12 at 21:52

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

• But $a-b$ and $b$ don't have the same set of divisors. They have the same set of common divisors with $a$. – Peter Taylor Jan 2 '12 at 14:29
• Ok common divisors. I always miss some details. – Norbert Jan 2 '12 at 14:40
• @Norbert : what you must have meant is that $\{a,b\}$ and $\{a-b,b\}$ have the same set of common divisors. – Michael Hardy Jan 2 '12 at 18:01
• Yes, this is what I meant. – Norbert Jan 2 '12 at 18:17
• Beware that this "repeated subtraction" implementation of division with remainder does not generally yield the Euclidean algorithm in other domains, e.g. for polynomials. See my comment to Hardy's answer. – Bill Dubuque Jan 2 '12 at 22:58

Let $A$ be a commutative ring. For any $a_1,\dots,a_n$ in $A$ let $(a_1,\dots,a_n)$ the ideal generated by the $a_i$.

Then, for any $q,b,r$ in $A$, we have $$(qb+r,b)=(b,r).$$ Indeed, $qb+r$ is in $(b,r)$, and $r$ is in $(qb+r,b)$.

EDIT. Dear Kevin: Your question, I think, would be better understood if put in a wider context, involving rings and ideals. The most basic fact behind the question is, I believe, the fact that, in any commutative ring, the elements $qb+r$ and $b$ generate the same ideal as the elements $b$ and $r$. If you make additional hypothesis, this fact can be interpreted in terms of divisibility. (See Bill's comment.) The simplest is to assume that your ring is a principal ideal domain.

I could try to explain this in greater details, but many mathematicians much better than I have already done that. So, my advice would be to take a look at at least one of the many Algebra textbooks written by great mathematicians. Here are some of these books:

• This seems to implicitly assume some relation between gcds and ideals, e.g. for Bezout domains $\rm\ (a,b) = (\gcd(a,b))\:.$ – Bill Dubuque Jan 2 '12 at 22:28
• Dear @Bill: Thanks for your comment. I edited the answer. (Of course, I agree with you.) – Pierre-Yves Gaillard Jan 3 '12 at 5:50
• Divisor theory gives one nice way to better understand the relations between ideals and gcds. For a brief overview see Friedemann Lucius, Rings with a theory of greatest common divisors and for a longer exposition see Olaf Neumann, Was sollen und was sind Divisoren? (What are divisors and what are they good for?), Math. Semesterber, 48, 2, 139-192 (2001). – Bill Dubuque Jan 3 '12 at 6:38
• Thank you for the neat explanation. Do you have a suggestion how I can update the question to involve rings and ideals? – www.data-blogger.com Mar 26 '18 at 8:06
• @www.data-blogger.com - Thank you! It's better, I think, to leave the question as it is. It's a nice question, and it has several outstanding answers (mine is not one of them). Users having answered the question in its original formulation, readers might be confused if you changed this formulation. – Pierre-Yves Gaillard Mar 26 '18 at 13:38

I'm going to use the notation $$(a,b)$$ for the GCD of $$a$$ and $$b$$.

If $$d|a$$ and $$d | b$$ then $$d|(a,b)$$, by the definition of GCD. (Well, by one common definition... if that's not the definition you learned, then you probably learned it as a theorem).

Since $$(a,b)|a$$ and $$(a,b)|b$$, by the definition of $$(a,b)$$, it divides $$r = a-qb$$, so we have $$(a,b)|r$$. This gives us $$(a,b)|b$$ and $$(a,b)|r$$, hence $$(a,b)|(b,r)$$.

Now let's go the other way. $$(b,r)|b$$ and $$(b,r)|r$$, both by definition, so it also divides $$r+qb$$, giving us $$(b,r)|a$$. That gives is $$(b,r)|(a,b)$$.

From $$(a,b)|(b,r)$$ and $$(b,r)|(a,b)$$, we get $$(a,b)=(b,r)$$ or $$(a,b)=-(b,r)$$. The latter can be eliminated because GCD is by definition greater than zero.

Theorem: Let $a > b > 0$ with $a = bq + r$, $0\leq{}r<b$ then $\gcd(a;b) = \gcd(b;r)$.

Proof: Need to show that $C(a;b) = C(b;r)$ for then the result will hold. To show that the two sets are equal requires showing that $C(a;b) \subseteq C(b;r)$ and that $C(b;r) \subseteq C(a;b)$:

Let $y \in C(a;b)$ thus $y|a$ and $y|b$,
then $y|[a+(-q)b]$,
and so $y|r$, since $r=a-bq$,
but since $y|b$ is also true, we now have that $y \in C(b;r)$, finally this means that $C(a;b) \subseteq C(b;r)$.

Now let $y \in C(b;r)$ thus $y|b$ and $y|r$,
then $y|[(q)b+r]$,
and so $y|a$, since $a=bq+r$,
but since $y|b$ is also true, we now have that $y \in C(a;b)$, finally this means that $C(b;r) \subseteq C(a;b)$.

Therefore the required results have been proven.

Note: Where $C(a;b)$ denotes the set of common divisors/factors of $a$ and $b$, that is: $C(a;b)=\{y: y|a \land y|b\}$

Let $$a = qb + r \implies a\equiv r (\text{ mod }b)\implies r = a\text{ mod }b$$

Bey GCD recursion theorem we have: $$\gcd\big(a, b\big) = \gcd\big(a, a\text{ mod } b\big)$$ Therefore

$$\gcd\big(a, b\big) = \gcd\big(a, a\text{ mod } b\big) = \gcd\big(a, r\big)$$

See reference

Bibliographic reference:
Thomas H. Cormen (2009). Introduction to Algorithms 3rd, 934.