$\gcd(a,b)$ compared to $\gcd(3a,b)$

Question

$\gcd(a,b)=\gcd(3a,b)$?

They are obviously not equal in general, as $\gcd(ax, bx)=|x|\gcd(a,b)$.

Answer 1

$$\gcd(3a,b) = \gcd(a,b)\gcd\left(3,\frac b{\gcd(a,b)}\right)$$

This is the specifics of the formula in the other answers - $\gcd(3a,b)=3\gcd(a,b)$ exactly when $3$ is a factor of $\frac{b}{\gcd(a,b)}$, otherwise $\gcd(3a,b)=\gcd(a,b)$.

More generally:

Theorem

$$\gcd(an,b) = \gcd(a,b)\gcd\left(n,\frac b{\gcd(a,b)}\right)$$

Proof: It's easy to show that the right hand side divides both $an$ and $b$.

Now, solve $$aU+bV=\gcd(a,b)\\nX+\frac{b}{\gcd(a,b)}Y=\gcd\left(n,\frac b{\gcd(a,b)}\right)$$

Multiply the second by $\gcd(a,b)$: $$n\gcd(a,b)X + bY = \gcd(a,b)\gcd\left(n,\frac b{\gcd(a,b)}\right)$$

On the left side, replace $\gcd(a,b)$ with $aU+bV$ to get:

$$anXU + b(Y+nXV) = \gcd(a,b)\gcd\left(n,\frac b{\gcd(a,b)}\right)$$

So any common divisor of $an$ and $b$ divides the right hand side, and we can easily show that the right hand side divides both $an$ and $b$.

Answer 2

If $\frac{b}{\text{gcd}(a,b)}$ is a multiple of 3 then $\text{gcd}(3a,b) = 3* \text{gcd}(a,b)$, else $\text{gcd}(3a,b) = \text{gcd}(a,b)$.