Why is $\gcd(a,b)=\gcd(b,r)$ when $a = qb + r$?

Question

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?

Answer 1

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

Answer 2

HINT $\rm\ \ $ If $\rm\ d\ |\ b\ $ then $\rm\ d\ |\ q\ b + r\ \iff\ d\ |\ r\:.\ $ Therefore $\rm\ \{b\:,\:q\ b+r\}\ $ and $\rm\ \{b\:,\: r\}\ $ have the same set of common divisors $\rm\:d\:,\:$ hence they have the same greatest common divisor.

Modly: $\ $ if $\rm\ b\equiv 0\ $ then $\rm\ q\ b+r\equiv 0\: \iff\: r\equiv 0\ \pmod{d}$

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.

Answer 3

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

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

Answer 5

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:

• Michael Artin, Algebra.

• Nathan Jacobson, Basic Algebra.

• Serge Lang, Algebra.

• Saunders Mac Lane, Garret Birkhoff, Algebra.

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

Answer 6

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 $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)|b$, 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 0.

Answer 7

a,b q ,r are integers how can we say that HCF(a,b) = HCF (b,r) we can say common divisor of a and b = common divisor of b and r. for example hcf of 4 and 2 = 2 4= 2x2 + o but here HCF of 4 and2 =2 but HCF of 2 and 0 =1 so how can we say that HCF(a,b) = HCF (b,r)