Proof that if $n>0$, $a=nm$, $b=np$, $c=nq$, then $\gcd(m,p,q)=1$ iff $n=\gcd(a,b,c)$

Question

I am trying to prove a three-integer version of the following number theoretic result for two integers:

Let $d > 0$, $a = da^{\prime}$, $b = db^{\prime}$, $a^{\prime}$, $b^{\prime} \in \mathbb{Z}$. Then, $a^{\prime}$ and $b^{\prime}$ are coprime if and only if $d=\gcd(a,b)$ (coprime meaning that $\gcd (a^{\prime}, b^{\prime}) = 1$).

Essentially, I am trying to do so in order to establish it as an intermediate result that I need in order to show the following:

Assuming $a$, $b$, $c$ $\neq 0$, determine when the Diopantine equation $ax+by+cz=d$ has a solution (in $\mathbb{Z})$.

Of course, this equation has a solution iff $\gcd(a,b,c)|d$, and of course, that question has been asked and answered before on this site - namely, here. But, what these solutions have in common is that they take for granted that for $n>0$, if $a=nm$, $b=np$, $c=nq$, ($m,p,q \in \mathbb{Z})$, then $\gcd(m,p,q)=1$ iff $n=\gcd(a,b,c)$ without actually proving that you can do this in the three-integer case.

In order to use this result, I'd like to prove it first. I'm not sure that for the way in which I want to use it, I need to prove it in both directions, but here's my attempt for the direction that $n = \gcd(a,b,c) \implies \gcd(m,p,q)=1$:

Suppose $n = \gcd(a,b,c)$. Then, $n|a$, $n|b$, $n|c$, or $a=nm$, $b=np$, $c=nq$.

By the associativity of $\gcd$ (already proven, but if you have a version of this proof that does not use the associativity of $\gcd$, that would be better), then $n = \gcd(\gcd(a,b),c) \implies n|\gcd(a,b),\, n|c \implies \gcd(a,b)=nr$, $c=nq$, where $r,q \in \mathbb{Z}$ and $\gcd(r,q)=1$.

But, since $\gcd(a,b)=nr,\,\,$ $nr|a,\,\,$ $nr|b,\,\,$ so $a=(nr)s,\,\,$ $b=(nr)t,\,\,$ $s,t\in \mathbb{Z},\,\,$ $\gcd(s,t)=1$.

Now, I somehow need to put this all together to show that $\gcd(r,q)=1,\,\,$ $\gcd(s,t)=1,\,\,$ implies that $\gcd(s,t,q)=1$ or that $\gcd(m,p,q)=1$ where $m$ and $p$ are multiples of $s$ and $t$, respectively. But, I need to do this in a rigorous way that isn't hand-wavey at all, and doesn't assume too much.

Could somebody please help me with this?

Thank you.

Answer 1

Observe that, \begin{align}\gcd(a,b,c)&=\gcd(\gcd(a,b),c)\tag{1}\\&= \gcd(\gcd(nm,np),nq)\\&=\gcd(n\gcd(m,p),nq)\\&=n\gcd(\gcd(m,p),q)\\&=n\gcd(m,p,q)\end{align}

Now we prove the following theorem,

Theorem. For $a,b,c\in \mathbb{Z}\setminus\{0\}$ there exists integers $x,y,z$ such that $$\gcd(a,b,c)=ax+by+cz$$

Proof. By Bezout's Theorem, from $(1)$ we can conclude that there exists integers $x_1,y_1$ such that, $$\gcd(a,b,c)=\gcd(a,b)x_1+cy_1\tag{2}$$ again by Bezout's Theorem we can conclude that there exists integers $x_2,y_2$ such that, $$\gcd(a,b)=ax_2+by_2\tag{3}$$Now substituting the value of $\gcd(a,b)$ obtained from $(3)$ in $(2)$ we see that $(2)$ becomes, \begin{align}\gcd(a,b,c)&=(ax_2+by_2)x_1+cy_1\\&=a(x_1x_2)+b(x_1y_2)+cy_1\end{align}All that is left now is to define $x= x_1x_2,y=x_1y_2$ and $z=y_1$.

Answer 2

I think the Bachet-Bézout identity will help you :

Let $a,b,c \in \mathbb{Z}\setminus\{0\}$, if $\gcd(a,b,c)=n$ then there exists $x,y,z \in \mathbb{Z}$ such that $ax+by+cz=d$.

To prove this we can consider the set $G=\{ax+by+cz\ / \ x,y,z \in \mathbb{Z}\}\cap (\mathbb{N}\setminus\{0\})$

This is a subset of $\mathbb{N}$. Non-empty because for instance $a\in G$ so there exists a minimum $n_0$ and there exists $x_0,y_0,z_0 \in \mathbb{Z}$ such that $n_0=ax_0+by_0+cz_0$.

Then we want to prove that $n_0$ divides $a,b,c$. We use the euclidian division :

$a=k_0 n_0 + r_0$ with $k_0\in \mathbb{Z}$ and $0<\vert r_0\vert <n_0$.

$a-k_0n_0=r_0\Leftrightarrow a-k_0(ax_0+by_0+cz_0)=(1-k_0x_0)a-k_0y_0b-k_0z_0=r_0$ which proves that $r_0\in G$ but by inequality from euclidian division $r_0=0$. We repeat the operation on $b,c$ and we find that $n_0$ divides $a,b,c$.

Now the last step is to show that $\gcd(a,b,c)=n=n_0$. Easy to see with the fact that $n$ divides $a,b,c$ and $n_0=ax_0+by_0+cz_0$.