Proving that $\gcd(a,ak+c)=\gcd(a,c)$

Question

I'm having some trouble proving the following proposition:

Let $a,c \in \mathbb Z\setminus\{0\} $ and $k \in \mathbb Z$, then:$$\gcd(a,ak+c)=\gcd(a,c)$$

If $D_a$ and $D_c$ are the set of all numbers that devide $a$ and $c$ respectively I was able to prove that, if $\lambda := \gcd(a,ak+c)$ then $\lambda \in D_a \cap D_c$, but now, I can't arrive at the conclustion that $\max(D_a \cap D_c) = \lambda$. How can I conclude this proof?

Answer 1

Let $d = \gcd(a,ak+c)$ and $d_{1}=\gcd(a,c)$.

We have that $d|a \implies d|ak$ so $d|(ak+c)-ak=c \implies d|d_{1}$.

$d_{1}|a \implies d_{1}|ak$. Since $d_{1}|c, d_{1}|ak+c$.

Hence $d|d_{1}$ and $d_{1}|d$ with $d,d_{1} > 0.$

Therefore $d = d_{1}.$

You may also use $d \leq d_{1}$ and $d_{1} \leq d \implies d=d_{1}$ instead.

Answer 2

HINT

Sufficient to prove $\gcd(a,c) = \gcd(a,a+c)$.

This is the basis for the Euclidean algorithm, which finds $\gcd(a,b)$ with $a>b$ as $\gcd(a,b) = \gcd(a-b,b)$.

Answer 3

By Bezout $g=au+cv=a(u-kv)+(ak+c)v$ and since $\begin{cases}g\mid a\\g\mid c\end{cases}\implies g\mid ak+c$ then $g=\gcd(a,ak+c)$