$\gcd(a,b)$ en comparación con $\gcd(3a,b)$

Question

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

Obviamente no son iguales en general, como $\gcd(ax, bx)=|x|\gcd(a,b)$.

Answer 1

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

Este es de los detalles de la fórmula en las otras respuestas - $\gcd(3a,b)=3\gcd(a,b)$ exactamente al $3$ es un factor de $\frac{b}{\gcd(a,b)}$, de lo contrario $\gcd(3a,b)=\gcd(a,b)$.

De manera más general:

Teorema de

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

Prueba: Es fácil demostrar que el lado derecho divide tanto a a$an$$b$.

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

Multiplique el segundo por $\gcd(a,b)$: $$n\gcd(a,b)X + bY = \gcd(a,b)\gcd\left(n,\frac b{\gcd(a,b)}\right)$$

En el lado izquierdo, reemplace $\gcd(a,b)$ $aU+bV$ para obtener:

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

Por lo que cualquier divisor común de a $an$ $b$ divide el lado derecho, y podemos demostrar fácilmente que el lado derecho divide tanto a a$an$$b$.

Answer 2

Si $\frac{b}{\text{gcd}(a,b)}$ es un múltiplo de 3, a continuación,$\text{gcd}(3a,b) = 3* \text{gcd}(a,b)$, otra cosa $\text{gcd}(3a,b) = \text{gcd}(a,b)$.