43
$\begingroup$

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.

$\endgroup$
9
  • 2
    $\begingroup$ $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. $\endgroup$ Jan 2, 2012 at 13:12
  • $\begingroup$ If you're asking about integers, then this question is very similar to yours: math.stackexchange.com/questions/59147/… $\endgroup$ Jan 2, 2012 at 13:16
  • $\begingroup$ see page 13 here www-groups.dcs.st-and.ac.uk/~martyn/teaching/1003/… $\endgroup$
    – Bhargav
    Jan 2, 2012 at 13:26
  • $\begingroup$ @Martin The result does not depend upon the underlying ring (assuming $\rm\:gcd(a,b)\:$ exists). $\endgroup$ Jan 2, 2012 at 18:19
  • $\begingroup$ @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. $\endgroup$ Jun 30, 2016 at 6:41

8 Answers 8

31
$\begingroup$

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.

$\endgroup$
1
  • 2
    $\begingroup$ Thank you! Extremely clear explanation :) $\endgroup$ Mar 26, 2018 at 8:03
21
$\begingroup$

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

$\endgroup$
6
  • $\begingroup$ Very clear answer! Little remark: $a-b \neq r$, but $a-qb = r$, but all your explanation will work using that :). $\endgroup$ Jan 2, 2012 at 21:17
  • 1
    $\begingroup$ @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. $\endgroup$ Jan 2, 2012 at 22:37
  • $\begingroup$ @Kevin : Thanks; I've fixed the typo. $\endgroup$ Jan 3, 2012 at 0:52
  • $\begingroup$ 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. $\endgroup$ Jan 3, 2012 at 0:53
  • $\begingroup$ 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. $\endgroup$ May 4, 2017 at 9:45
13
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ excellent answer, +1 for it. $\endgroup$ Jan 2, 2012 at 13:44
  • $\begingroup$ Thanks, but why do they have the same common divisors? $\endgroup$ Jan 2, 2012 at 21:15
  • 2
    $\begingroup$ @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$. $\endgroup$ Jan 2, 2012 at 21:52
6
$\begingroup$

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

$\endgroup$
6
  • 2
    $\begingroup$ But $a-b$ and $b$ don't have the same set of divisors. They have the same set of common divisors with $a$. $\endgroup$ Jan 2, 2012 at 14:29
  • $\begingroup$ Ok common divisors. I always miss some details. $\endgroup$
    – Norbert
    Jan 2, 2012 at 14:40
  • 1
    $\begingroup$ @Norbert : what you must have meant is that $\{a,b\}$ and $\{a-b,b\}$ have the same set of common divisors. $\endgroup$ Jan 2, 2012 at 18:01
  • 1
    $\begingroup$ 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. $\endgroup$ Jan 2, 2012 at 22:58
  • 1
    $\begingroup$ Thanks, for this warning. I believed that this appraoch works in all cases. $\endgroup$
    – Norbert
    Jan 2, 2012 at 23:03
4
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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:

In short, my advice is the classic: Read the masters!

$\endgroup$
5
  • $\begingroup$ This seems to implicitly assume some relation between gcds and ideals, e.g. for Bezout domains $\rm\ (a,b) = (\gcd(a,b))\:.$ $\endgroup$ Jan 2, 2012 at 22:28
  • $\begingroup$ Dear @Bill: Thanks for your comment. I edited the answer. (Of course, I agree with you.) $\endgroup$ Jan 3, 2012 at 5:50
  • 2
    $\begingroup$ 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). $\endgroup$ Jan 3, 2012 at 6:38
  • $\begingroup$ Thank you for the neat explanation. Do you have a suggestion how I can update the question to involve rings and ideals? $\endgroup$ Mar 26, 2018 at 8:06
  • $\begingroup$ @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. $\endgroup$ Mar 26, 2018 at 13:38
2
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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