[Math] 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$.