Is it true that for any integer $c_1, c_2$, we have $\gcd(n_1, n_2, n_3) = \gcd(n_1, n_2, c_1 n_1 + c_2 n_2 + n_3)$ for $n_1, n_2, n_3 \in \mathbb N$?

Question

I got this task to check that if $n_1, n_2, n_3 \in \mathbb{N}$ the $\text{gcd}(n_1, n_2, n_3) =\text{gcd}(n_1, n_2, c_1n_1 + c_2n_2 + n_3)$ is valid for any $c_1, c_2 \in \mathbb{Z}$.

I started the idea saying that if:

$\text{gcd}(n_1, n_2, n_3) = k$, only if:

$k|n_1 \land k|n_2 \land k|n_3$ which means that: $$ \left\{ \begin{array}{c} n_1=ke \\ n_2=kf \\ n_3=kg \end{array} \right. \quad e, f, g\in \mathbb{N} $$ Now $gcd(n_1, n_2, c_1n_1 + c_2n_2 + n_3) = k$ only if: $$ c_1n_1 + c_2n_2 + n_3 = kr, \quad r \in \mathbb{Z} $$ Substituting the values of $n_1, n_2, n_3$: $$ k(c_1e + c_2f + g) = kr $$ Which means that it is valid only if:$$c_1e + c_2f + g = r$$ But now I got stucked, I cannot say if this is valid for any $c_1, c_2$, could anyone help?

Answer 1

I suppose that you have to proof that $gcd(n_1,n_2,n_3)=gcd(n_1,n_2,c_1n_1+c_2n_2+n_3)$, (not $c_3$ at the end... Who is $c_3$?)

$gcd(n_1,n_2,n_3)=k$;

$gcd(n_1,n_2,c_1n_1+c_2n_2+n_3)=p$.

$k$ divides $n_1$,$n_2$ and $n_3$.

So $k$ divides $n_1$,$n_2$,$c_1n_1+c_2n_2+n_3$.

So $k$ divides $p$.

But $p$ divides $n_1$,$n_2$,$c_1n_1+c_2n_2+n_3$. It suffices to show that $p$ divides also $n_3$. This is clear:

$n_1=ps_1$, $n_2=ps_2$, $c_1n_1+c_2n_2+n_3=ps_3$.

So $n_3=ps_3-c_1n_1-c_2n_2=p(s_3-c_1s_1-c_2s_2)$.

So $p$ divides $k$.

So $gcd(n_1,n_2,n_3)=gcd(n_1,n_2,c_1n_1+c_2n_2+n_3)$.

Answer 2

Let $d_1 = \gcd (n_1, n_2, n_3), d_2 = \gcd (n_1, n_2, c_1 n_1 + c_2 n_2 + n_3)$. We want to show $d_1 = d_2$.

I will prove $d_2 | d_1$. Then you can do $d_1 | d_2$ similarly then you are done.

There exists $x_1, x_2, x_3 \in \mathbb{Z}$ such that $$ x_1 n_1 + x_2 n_2 + x_3 n_3 =d_1. $$

Therefore $$ (x_1 - x_3 c_1) n_1 + (x_2 - x_3 c_2)n_2 + x_3 (c_1 n_1 + c_2 n_2 + n_3) =d_1 \Rightarrow d_2 | d_1. $$

Answer 3

$${\rm RHS} =\:\! \overbrace{((n_1,n_2),\,c_1n_1\!+\!c_2n_2\!+\!n_3) = ((n_1,n_2), \color{#c00}{n_3})}^{\textstyle\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\! \bmod d\!=\!\color{#0a0}{(n_1,n_2)}\!:\, c_1\color{#0a0}{n_1}\!+\!c_2\color{#0a0}{n_2}\!+\!\color{#c00}{n_3}\equiv \color{#c00}{n_3} } =\:\! \rm LHS\qquad$$

via gcd mod reduction: $\,(d,n,\ldots) = (d,\color{#c00}{\bar n},\ldots)\, $ if $\, n\equiv \color{#c00}{\bar n}\pmod{\!d},\,$ and gcd associative law.

Similarly a gcd stays the same if we replace any argument by any integer congruent to it mod the gcd of (some of) the other arguments. That's essentially the Euclidean algorithm reduction step.