Proving $\gcd(ga, gb) = g\gcd(a, b)$ intuitively

Question

I am trying to derive by myself $$ \gcd(ga, gb) = g\gcd(a,b), $$
but I am stuck proving it fully. Note, that I avoided reading the relevant proof as I am trying to improve my intuition on the process and the proof, so I want to understand if my approach is a dead end or what am I missing to complete it.

My approach is the following:

$GCD(a, b) \implies GCD(a, b) | a \equiv x\cdot GCD(a, b) = a$
similarly
$GCD(a, b) \implies GCD(a, b) | b \equiv y\cdot GCD(a, b) = b$

But
$GCD(a, b) | a \implies GCD(a, b) | ga$
similarly
$GCD(a, b) | b \implies GCD(a, b) | gb$

So it has been proven so far that $GCD(a, b)$ is a common divisor of $ga$ and $gb$. Additionally it is implied that the $GCD(g\cdot a, g\cdot b)$ is a multiple of $GCD(a, b)$ because:

$x\cdot GCD(a,b) = a \equiv g\cdot x\cdot GCD(a,b) = g\cdot a \implies g\cdot a = x \cdot (g \cdot GCD(a,b))$

$y\cdot GCD(a,b) = b \equiv g\cdot y\cdot GCD(a,b) = g\cdot b \implies g\cdot b = y \cdot (g\cdot GCD(a,b))$

Combining the above we can see that $g\cdot GCD(a,b)$ is a common divisor of $ga$ and of $gb$.
But I am stuck here on what step am I missing to prove that it is also the greatest common divisor.

Update
Based on the comment of @user2661923 I thought of the following:

$GCD(a, b) \implies GCD(a, b) | a \equiv x\cdot GCD(a, b) = a$
similarly
$GCD(a, b) \implies GCD(a, b) | b \equiv y\cdot GCD(a, b) = b$

Now for any $d$ where $d |a \And d|b$ i.e. $d$ is a common divisor this implies that $d | GCD(a,b)$ by definition.

Now since:
$d \mid a \Leftrightarrow g\cdot d \mid g\cdot a$
and
$d \mid b \Leftrightarrow g\cdot d \mid g\cdot b$
and
$d \mid GCD(a,b) \Leftrightarrow g\cdot d \mid g\cdot GCD(a,b)$

this proves that $g\cdot GCD$ is also the $GCD$ of $g\cdot a, g\cdot b$

Is this proof correct? I kind of think that I am proving it starting with what I am trying to prove ($d \mid a \Leftrightarrow g\cdot d \mid g\cdot a$)

Answer 1

To prove:

$\text{gcd}(ga,gb) = g \times \text{gcd}(a,b)$.

---

Given:
By definition, $d = \text{gcd}(a,b) \iff$:

1. $d|a, d|b$
2. For any common divisor $e$ such that $e|a, e|b$, you have that $e|d$.

By definition, for $d,r \in \Bbb{Z^+}, ~d|r \iff \exists s \in \Bbb{Z^+}$ such that $(d \times s) = r.$

---

Lemma 1
For $d,r,g \in \Bbb{Z^+}, d|r \iff (gd) | (gr).$

Proof

$\implies:$
$d|r \implies \exists s$ such that $ds = r \implies gds = gr \implies gd | gr.$

$\impliedby:$
$gd|gr \implies \exists s$ such that $gds = gr \implies ds = r \implies d | r.$

---

Let $p = \text{gcd}(ga,gb),~~$ and let $~~q = \text{gcd}(a,b).$

Using the definitions and the Lemma, you have that $q|a, q|b.$

This implies that $gq|ga$ and that $gq | gb$. Thus, $(gq)$ is a common divisor to $(ga)$ and $(gb)$. Thus, by definition $(gq) ~| ~\text{gcd}(ga,gb) = p.$

Suppose that $(gq) \neq p$.
Then:

1. $(gq) < p$.
2. $g | p \implies \exists s$ such that $gs = p.$

Therefore, since $gs = p > gq$, you have that $s > q$.

Further, since $p|ga$ and $p | gb$, you have that
$gs | ga$ and $gs | gb$.

Therefore:

1. $s|a$ and $s|b$.
2. $s > q$.

This yields a contradiction, because, by definition, since $q$ is the $\text{gcd}(a,b)$ then any other common divisor (namely $s$) must be a divisor of $q$. This is impossible, since $s > q$.

Therefore, the assumption that $gq \neq p$ led to a contradiction.

Therefore, $gq = p$.
Therefore $g \times \text{gcd}(a,b) = \text{gcd}(ga,gb)$.