Show that $\gcd(ab+c,ca+b,bc+a)=\gcd(a,b,c)$ if $\gcd(a^2-1,b^2-1,c^2-1)=1$

Question

The problem is, as in the title:

Given $a$, $b$, $c$ are positive integers so that $\gcd(a^2-1,b^2-1,c^2-1)=1$. Prove $\gcd(ab+c,ca+b,bc+a)=\gcd(a,b,c)$.

So far I have only proved that the second GCD divides the first GCD. Here's my work:

Let $\gcd(a,b,c)=d_1$, $\gcd(ab+c,ca+b,bc+a)=d_2$. From that we know $d_1|a,b,c$, that means $d_1|ab+c,ca+b,bc+a$. Thus, $d_2|d_1$.

The other way I haven't figured it out yet, I think because I haven't used the given $\gcd(a^2-1,b^2-1,c^2-1)=1$ stated in the problem, and I'm not used to working with the GCD of 3 numbers. Any hint would be greatly appreciated and thanks in advance.

Answer 1

$\!\bmod\!$ first gcd $\,d\!:\,\ 0\equiv \overbrace{\color{#0a0}c\:\!a\!+\!b\equiv -\color{#0a0}b(\color{#0a0}a^2\!-\!1)}^{\textstyle \color{#0a0}{c\equiv -ab}\ \ \ } = -b\:\!\bar a,\ \ \bar x:=x^2\!-\!1$.

Thus $\:d\mid b\bar a\Rightarrow d\mid \color{#c00}{(b,d)}\bar a= \color{#c00}{(a,b,c)}\bar a,\,$ i.e. $\,\bbox[5px,border:1px solid #c00]{d\mid e\bar a}\:\!,\ \ e := (a,b,c)$.

$\underbrace{a,b,c\,\ \rm symmetry}_{\large \text{i.e. a "similar" proof}}\Rightarrow \bbox[5px,border:1px solid #c00]{d\mid e\bar b,e\bar c}\ $ so $\ d\mid e\!\!\underbrace{(\bar a,\bar b,\bar c)}_{\large \text{assumed}\ =1}\!\!\! = e.\ \ \ \small\bf QED$

Answer 2

Let $d=\gcd(a,b,c)$ and let $e=\gcd(bc+a,ca+b,ab+c)$.

Our goal is to show $e=d$.

First a lemma . . .

Lemma:$\;$If $p$ is prime and $p{\,\mid\,}e$, then $p{\,\mid\,}d$.

Proof of the lemma:

Suppose $p$ is prime and $p{\,\mid\,}e$.

From $\gcd(a^2-1,b^2-1,c^2-1)=1$, it follows that at least one of $a^2-1,b^2-1,c^2-1$ is not a multiple of $p$.

Assume $p{\,\not\mid\,}(c^2-1)$.

\begin{align*} \text{Then}\;\;& p{\,\mid\,}e \\[4pt] \implies\;& p{\,\mid\,}(bc+a),\;\;p{\,\mid\,}(ca+b) \\[4pt] \implies\;& bc\equiv -a\;(\text{mod}\;p),\;\;ca\equiv -b\;(\text{mod}\;p) \\[4pt] \implies\;& c^2ab\equiv ab\;(\text{mod}\;p) \\[4pt] \implies\;& ab(c^2-1)\equiv 0\;(\text{mod}\;p) \\[4pt] \implies\;& ab\equiv 0\;(\text{mod}\;p) \\[4pt] \implies\;& p{\,\mid\,}ab \\[4pt] \implies\;& p{\,\mid\,}\bigl((ab+c)-ab\bigr) \\[4pt] \implies\;& p{\,\mid\,}c \\[4pt] \implies\;& p{\,\mid\,}\bigl((bc+a)-bc\bigr),\;\;p{\,\mid\,}\bigl((ca+b)-ca\bigr) \\[4pt] \implies\;& p{\,\mid\,}a,\;\;p{\,\mid\,}b \\[4pt] \end{align*} Thus $p{\,\mid\,}a,\;p{\,\mid\,}b,\;p{\,\mid\,}c$, so $p{\,\mid\,}d$.

This completes the proof of the lemma.

Returning to the main proof, write $$ \left\lbrace \begin{align*} a&=da_1\\[4pt] b&=db_1\\[4pt] c&=dc_1\\[4pt] \end{align*} \right. $$ where $\gcd(a_1,b_1,c_1)=1$.

Then we get $$ e=d{\,\cdot\,}\gcd(db_1c_1+a_1,dc_1a_1+b_1,da_1b_1+c_1) $$ so it remains to show $\gcd(db_1c_1+a_1,dc_1a_1+b_1,da_1b_1+c_1)=1$.

Suppose instead that $\gcd(db_1c_1+a_1,dc_1a_1+b_1,da_1b_1+c_1) > 1$.

Let $p$ be a prime factor of $\gcd(db_1c_1+a_1,dc_1a_1+b_1,da_1b_1+c_1)$.

Then $p{\,\mid\,}e$, so by the lemma, we get $p{\,\mid\,}d$, hence $$ \left\lbrace \begin{align*} & p{\,\mid\,}\bigl((db_1c_1+a_1)-db_1c_1\bigr) \\[4pt] & p{\,\mid\,}\bigl((dc_1a_1+b_1)-dc_1a_1\bigr) \\[4pt] & p{\,\mid\,}\bigl((da_1b_1+c_1)-da_1b_1\bigr) \\[4pt] \end{align*} \right. $$ But that gives $p{\,\mid\,}a_1,\;p{\,\mid\,}b_1,\;p{\,\mid\,}c_1$, contrary to $\gcd(a_1,b_1,c_1)=1$.

Hence $\gcd(db_1c_1+a_1,dc_1a_1+b_1,da_1b_1+c_1)=1$, so $e=d$, as was to be shown.