1
$\begingroup$

I am studying divisibility and greatest common divisors. I have reached a section where I need to prove properties. My question is: are my proofs substantial? Or do I need to add to them? Below are two of the properties that I am trying to prove along with my progress. Please help if you are able to, thanks.

a) Prove that $\gcd(a, a – b) = d$

b) Prove that $\gcd(b, a – bq) = d$ for any $q ∈ Z$


$a)$ $\gcd(a, b) = d$.

Let $a = md$ and $b = nd$ where $m$ and $n$ are coprime.

This leads to $a – b = md – nd = d(m – n)$

$∴\gcd(a,a-b)=d$


b) $\gcd(a, b) = d$.

Let $a = md$ and $b = nd$ where $m$ and $n$ are coprime

$⇒ qb = qnd$ for any integer $q$

$a - bq = a – qnd = md – qnd = d(m – qn)$

$∴\gcd(b, a - bq) = d$

$\endgroup$
  • 2
    $\begingroup$ In both cases, you have shown that $d$ is a common divisor of the two things, but not that it is the greatest common divisor. $\endgroup$ – rogerl Aug 13 '15 at 15:15
  • $\begingroup$ You've got half of each proof, that $d$ is a common divisor, but you have not shown that it is the greatest. $\endgroup$ – Michael Dyrud Aug 13 '15 at 15:16
  • $\begingroup$ Ok then, how would I show that d is the greatest common divisor? Could I say for a) that m and n are co-prime with each other and a and b? I am unsure of how to show it for b). $\endgroup$ – Mathematica Aug 13 '15 at 15:34
0
$\begingroup$

For each of the problems you've shown that $d$ is a common divisor of the two things. You still need to show that it's the greatest common divisor.

I'm not sure what definition you've been given of the greatest common divisor, but one which is useful for problems like this is:

The greatest common divisor of two integers $a,b$ is an integer $d$ such that

  1. $d$ is a common divisor of $a,b$ and
  2. if $m$ is any other common divisor of $a,b$, then $m\mid d$.

You should be able to check that if $d$ is the greatest common divisor in this (possibly) new sense, then it is greater than all the other common divisors.

Conversely, if $d = \mathrm{gcd}(a,b)$, and $m$ is another common divisor, then since $d$ and $\frac{m}{\mathrm{gcd}(d,m)}$ are coprime, it follows that $$d\frac{m}{\mathrm{gcd}(d,m)}$$ is a divisor of $a,b$. Since $d$ is the greatest common divisor, we must have $\mathrm{gcd}(d,m)= m$. We deduce that $m\mid d$.


This definition suggests a proof strategy, which we can apply to part (a):

You've already shown already shown that $d$ is a common divisor of $a$ and $a-b$. It remains to show part 2 of the definition.

Suppose $m$ is another common divisor of $a$ and $a-b$.

  1. Can you show directly that $m \mid b$? If so, then $m$ is a common factor of $a,b$.
  2. Using part 2 of the definition, since $d = \mathrm{gcd}(a,b)$, we have $m \mid d$.
  3. So any common factor $m$ of $a$ and $a-b$ also divides $d$. Hence $d$ is the gcd.
$\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.