I've tried a couple of things trying to solve this problem but I get no answer.
These are one of the few things I know about “Gcd” and division:
If $a\mid b$ and $a \mid c$, then $a \mid b \cdot x + c \cdot y$ for any $x, y \in \mathbb{Z}$.
I also know that if $a$ divides $b$ and $c$, also divides its sum and it’s subtraction.
“gcd” also represents the minor linear combination.
I’d really appreciate your help, thank you.
On
Let $g = \gcd(a,c)$. Since $g \mid a$ and $g \mid c$, we get $g \mid ad-bc$. Since $ad-bc \mid a$ and $ad-bc \mid c$, then $ad-bc$ is a common divisor of $a$ and $c$, so $ad-bc \mid g$. Now, $g \mid ad-bc$, and $ad-bc \mid g$. So $g = \pm (ad-bc)$. For simplicity let's assume $g = ad-bc$. (If $g = -(ad-bc)$, then either go through a similar argument to the following, or else relabel $(a,b,c,d) \to (c,d,a,b)$, which makes $ad-bc \to cb-da$.)
Now we have $ad-bc = g$. So $(a/g)d - b(c/g) = 1$, where $a/g, d, b, c/g$ all are positive integers.
Finally, consider the combination: $$ (-c/g)(an+b) + (a/g)(cn+d) = (-c/g)b + (a/g)d $$ which equals $1$. Can you finish the proof from here?
On
By hypothesis $\ \delta := ad\!-\!bc\mid a,c,\ $ therefore $\,1 = d(a/\delta)-b(c/\delta)\,\Rightarrow\,\color{#c00}{(b,d)\,=\,1}\,$ so by $\rm\color{#0a0}{Euclid}$
$a(cn\!+\!d) -c(an\!+\!b) = \delta$ $\,\Rightarrow\, (an\!+\!b,cn\!+\!d) =\underbrace{(an\!+\!b,cn\!+\!d,\,\color{#0a0}\delta) = (\color{#c00}{b,d},\delta)}_{\!\!\!\large \begin{align}&an+b\ \,\equiv\,\ \color{#c00}b\,\color{#0a0}{\pmod{\!\delta}}\ \ {\rm by}\ \ \delta\ \mid\ a\\ &cn+d\ \,\equiv\,\ \color{#c00}d\,\color{#0a0}{\pmod{\!\delta}}\ \ {\rm by}\ \ \delta\ \mid\ c\end{align} }\!\color{#c00}{ = 1}$
Or $\,\ (a/\delta)(cn\!+\!d) -(c/\delta) (an\!+\!b) = 1\,\Rightarrow\, (an\!+\!b,cn\!+\!d)=1\ $ as in the first line.
Remark $\ $ We used $\ (k,\delta) = (k',\delta)\ $ if $\ k\equiv k'\color{#0a0}{\pmod{\!\delta}}\,\ $ [i.e. Euclidean algorithm]
and further we used $\, (j,k) = (j,k, ak\!-\!cj)\,$ by prior, using $\, ak\!-\!cj\equiv 0\pmod{\!j,k}$
On
Suppose $a,b,c,d$ are positive integers such that $$ \begin{cases} (ad - bc){\,|\,}a\\[4pt] (ad - bc){\,|\,}c \end{cases} \qquad $$ Fix a positive integer $n$.
Let $g=\gcd(an+b,cn+d)$.
Our goal is to show $g=1$.
Let $h=\gcd(a,c)$.
Letting $a_1=a/h$ and $c_1=c/h$, we get $$ \begin{cases} a=ha_1\\[4pt] c=hc_1\\ \end{cases} \qquad\;\;\;\;\;\;\, $$ where $a_1,c_1$ are positive integers such that $\gcd(a_1,c_1)=1$.
\begin{align*} \text{Then}\;\;& \begin{cases} (ad - bc){\,|\,}a\\[4pt] (ad - bc){\,|\,}c \end{cases} \qquad\qquad\;\;\; \\[4pt] \implies\;& \begin{cases} (a_1d - bc_1){\,|\,}a_1\\[4pt] (a_1d - bc_1){\,|\,}c_1 \end{cases} \\[4pt] \implies\;& |a_1d - bc_1|=1 \\[4pt] \implies\;& |ad - bc|=h \\[4pt] \end{align*} Also, from $|a_1d - bc_1|=1$, we get $\gcd(b,d)=1$. \begin{align*} \text{Then}\;\;& \begin{cases} g{\,|\,}(an+b)\\[4pt] g{\,|\,}(cn+d)\\ \end{cases} \\[4pt] \implies\;&g{\,|\,}\bigl(a(cn+d)-c(an+b)\bigr)\\[4pt] \implies\;&g{\,|\,}(ad-bc)\\[4pt] \implies\;&g{\,|\,}h\\[4pt] \implies\;&g{\,|\,}a\;\;\text{and}\;\;g{\,|\,}c\\[4pt] \end{align*} Then from $g{\,|\,}a$ and $g{\,|\,}(an+b)$, we get $g{\,|\,}b$.
Similarly, from $g{\,|\,}c$ and $g{\,|\,}(cn+d)$, we get $g{\,|\,}d$.
But then since $\gcd(b,d)=1$, it follows that $g=1$, as was to be shown.
Suppose that $a = x(ad-bc)$ and $c = y(ad-bc)$. Then $$ad-bc = [x(ad-bc)] \cdot d - b[y(ad-bc)] = (dx - by) (ad - bc).$$ However, since $(ad-bc) \mid a$, and $a$ is positive, it follows that $ad - bc \ne 0$. Thus, we must have that $dx - by = 1$, from which we can conclude that $\gcd(b,d) = 1$ (which proves the case of $n = 0$).
Now, for the general case, note that $a(cn+d) - (an+b)c = ad-bc$ so it divides both $a$ and $c$. Therefore, by the previous paragraph with $a' := a$, $b' := an+b$, $c' := c$, $d' := cn+d$, we get $\gcd(b', d') = 1$, i.e. $\gcd(an+b, cn+d) = 1$.