Divisibility proofs for greatest common divisor

Question

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$

Answer 1

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.