Prove that $∀a, b, c ∈ \mathbb Z$ with $b \neq 0$, if $b|c$, then $\gcd(a, b) = \gcd(a + c, b)$.

Question

Prove that $∀a, b, c ∈ \mathbb Z$ with $b \neq 0$, if $b|c$, then $\gcd(a, b) = \gcd(a + c, b)$.

I've proved it in the following way:

$\gcd(c,b) = b.$
Let $\gcd(a,b) = x$, $x|a$ and $x|b$
Since $b$ is the $\gcd$ of $c$,
if $x|b$ then $x|c$

Thus, $\gcd(a+c, b) = x = \gcd(a, b)$.

Was wondering if this is a solid proof. If not, is there anyway I can improve on this? Thanks for helping out

Answer 1

Let $d=\gcd(a,b)$. Then since $b | c$, we have $d|c$ which implies $d| a+c$. Thus, $k=\gcd(a+c,b)\ge d$.

Now, $k | b$ and $k|a+c$. But $k|b \Rightarrow k|c \Rightarrow k|a$ (Because $k$ also divides $a+c$). Thus, we have $k$ divides both $a$ and $b \Rightarrow k\le d$

In conclusion, $k\le d $ and $k \ge d$ implies $k=d$, which was what was to be proved!

Answer 2

The conclusion $\gcd(a+c, b) = x = \gcd(a, b)$ is not that clear from your previous parts.

One way to show the claim $\gcd(a, b) = \gcd(a + c, b)$ is to split the task into two parts:

$\qquad\qquad\gcd(a, b)|\gcd(a + c, b)\qquad$ and $\qquad\gcd(a+c, b)|\gcd(a, b)$

from which equality follows.

We obtain \begin{align*} \begin{array}{rlr} \gcd(a,b)|b&\qquad\qquad(\text{by definition of }\gcd)&\qquad (1)\\ b|c&\qquad\qquad(\text{by assumption})\\ \Longrightarrow \gcd(a,b)|c&\qquad\qquad(\text{by transitivity of }|)&\qquad(2)\\ \\ \gcd(a,b)|a&\qquad\qquad(\text{by definition of }\gcd)&\qquad(3)\\ \\ \Longrightarrow \gcd(a,b)|(a+c)&\qquad\qquad(\text{by(2) and (3)})&\qquad(4)\\ \\ \color{blue}{\Longrightarrow \gcd(a,b)|\gcd(a+c,b)}&\qquad\qquad(\text{by(1) and (4)})&\qquad\color{blue}{(\text{I})}\\ \end{array} \end{align*}

We further obtain \begin{align*} \begin{array}{rlr} \gcd(a+c,b)|b&\qquad\qquad(\text{by definition of }\gcd)&\qquad(5)\\ b|c&\qquad\qquad(\text{by assumption})\\ \Longrightarrow \gcd(a+c,b)|c&\qquad\qquad(\text{by transitivity of }|)&\qquad(6)\\ \\ \gcd(a+c,b)|(a+c)&\qquad\qquad(\text{by definition of }\gcd)&\qquad(7)\\ \\ \Longrightarrow \gcd(a+c,b)|a&\qquad\qquad(\text{by(6) and (7)})&\qquad(8)\\ \\ \color{blue}{\Longrightarrow \gcd(a+c,b)|\gcd(a,b)}&\qquad\qquad(\text{by(5) and (8)})&\qquad\color{blue}{(\text{II})}\\ \end{array} \end{align*}

We conclude from (I) and (II) \begin{align*} \color{blue}{\gcd(a,b)=\gcd(a+c,b)} \end{align*}