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

  • 0
    @BillDubuque I think that it would be better to close as$a$duplicate in the opposite direction ([706016](http://math.stackexchange.com/questions/706016/prove-that-gcda-b-gcda-b-ma) $\to$ [95799](http://math.stackexchange.com/questions/95799) rather than 95799 $\to$ 706016). I think that the post which is the most useful should be left open, as [discussed on meta](http://meta.math.stackexchange.com/a/16418). And this question has more answers and some answers are more detailed. I have also mentioned this [in chat](http://chat.stackexchange.com/transcript/message/30715294#30715294).2016-06-30

8 Answers 8

26

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.

  • 1
    Thank you! Extremely clear explanation :)2018-03-26
18

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

  • 0
    Also, why do we need both parts of this answer? is it not sufficient to show that an arbitrary factor of both (a, b) must also be a factor of (b, a-qb)? If not can you please explain why?2017-05-04
11

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

  • 1
    @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$.2012-01-02
4

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, you can apply this equality $q$ times and obtain $\operatorname{gcd}(a,b)=\operatorname{gcd}(r,b)$

  • 0
    Thanks, for this warning. I believed that this appraoch works in all cases.2012-01-02
2

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.

1

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!

  • 0
    @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.2018-03-26
1

Theorem: Let $a > b > 0$ with $a = bq + r$, $0\leq{}r 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\}$

0

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.