Euclidean Algorithm Computation Given positive integers $a,b,c,d$, find all possible values of $|ad - bc|$ for which $$\gcd (an + b, cn + d) = m$$ for positive integer $m>1$, has infinitely many values for $n$. 
My progress thus far: I tried working with small values of $a,b,c,d$ first. It appears to me that it is impossible for a the numbers to be $a>b>c = d$ or $a> b = c = d$ or $a=b=c=d$ (or some permutation but with those relations), but I'm not sure. For example, say we take $(1,1,1,2)$ (a quadruple representing $(a,b,c,d)$), then by the Euclidean algorithm, we have that 
$$\gcd (n + 1 , n+2) = \gcd(n+1, 1) = m,$$
which consequently doesn't have any solutions unless $m=1.$ But I'm not quite sure if this is correct -- I can't prove that those relationships between the variables are true -- nor can I make much further progress than just playing with numbers. I would greatly appreciate any help. Thank you. 
 A: Consider for some positive integers $a$, $b$, $c$ and $d$ that there's an $m \gt 1$ such that
$$m = \gcd(an + b, cn + d) \tag{1}\label{eq1A}$$
for at least one integer $n$. Thus, for some integers $e$ and $f$ with $\gcd(e,f) = 1$, you get
$$an + b = em \tag{2}\label{eq2A}$$
$$cn + d = fm \tag{3}\label{eq3A}$$
Next, $a$ times \eqref{eq3A} minus $c$ times \eqref{eq2A} gives
$$ad - bc = (af - ec)m \tag{4}\label{eq4A}$$
This shows $m \mid ad - bc$. If $ad - bc = 0$, then for $m \gt 1$, you have $af - ec = 0 \implies af = ec$. Since $\gcd(e,f) = 1$, then $e \mid a$ and $f \mid c$. Since $a$ and $c$ are fixed integers, there are only a finite # of possible values for $e$ and $f$, so there can't be an infinite # of $n$.
From this point on, assume $ad - bc \neq 0$. Next, let
$$g = \gcd(a,c) \implies a = gh, c = gi, \gcd(h,i) = 1 \tag{5}\label{eq5A}$$
Note $af - ec$ must be an integral multiple of $g$, so $m \mid \frac{ad - bc}{\gcd(a,c)} = hd - ib$. Thus, $m \gt 1$ requires $|ad - bc| \gt \gcd(a,c) = g$. Assume this is true, i.e., a required condition is that
$$\frac{|ad - bc|}{\gcd(a,c)} \gt 1 \tag{5B}\label{eq5B}$$
Also have 
$$m = |hd - ib| \tag{6}\label{eq6A}$$
Next, have
$$j = \text{sgn}(ad - bc) \tag{7}\label{eq7A}$$
where $\text{sgn}$ is the Sign function, meaning it's $1$ if the argument is positive, $0$ if it's $0$, else its $-1$ if it's negative. From \eqref{eq4A}, \eqref{eq5A}, \eqref{eq6A} and \eqref{eq7A} you get
$$hf - ei = j \tag{8}\label{eq8A}$$
Since $\gcd(h,i) = 1$, Bézout's identity guarantees there's a solution, with the full set of solutions being
$$e = e_0 + kh \tag{9}\label{eq9A}$$
$$f = f_0 + ki \tag{10}\label{eq10A}$$
for some fixed integers $e_0$ and $f_0$, and $k$ being any integer. Note substituting \eqref{eq9A} and \eqref{eq10A} into \eqref{eq2A} and \eqref{eq3A} results in $2$ linear equations in the $2$ unknowns of $k$ and $n$. If the $2$ equations were linearly independent, you'd get just one solution for $k$ and $n$. Thus, an infinite # of values of $n$ requires the $2$ equations to be linearly dependent, i.e., one is a multiple of the other. To check on this, substitute \eqref{eq5A}, \eqref{eq9A} and \eqref{eq10A} into \eqref{eq2A} and \eqref{eq3A}, move the right side terms to the left, and gather the terms involving $n$ and $k$ together to get
$$(gh)n + (-hm)k + (b - e_0 m) = 0 \tag{11}\label{eq11A}$$
$$(gi)n + (-im)k + (d - f_0 m) = 0 \tag{12}\label{eq12A}$$
As can be seen, multiplying \eqref{eq11A} by $i$ and \eqref{eq12A} by $h$ causes the first $2$ terms to be equal. Thus, you also require (where \eqref{eq8A} is used below) that
$$\begin{equation}\begin{aligned}
i(b - e_0 m) & = h(d - f_0 m) \\
ib - (ie_0)m & = hd - (hf_0)m \\
(hf_0 - ie_0)m & = hd - ib \\
jm & = hd - ib
\end{aligned}\end{equation}\tag{13}\label{eq13A}$$
This matches \eqref{eq6A}, so there's no extra requirement for \eqref{eq2A} and \eqref{eq3A} to be multiples of each other. Thus, just use the updated version of \eqref{eq2A} in \eqref{eq11A} to get
$$(gh)n = (hm)k + (e_0 m - b) \tag{14}\label{eq14A}$$
From \eqref{eq6A} and \eqref{eq7A}, you have $m = j(hd - ib)$, so this means
$$\begin{equation}\begin{aligned}
e_0 m - b & = e_0 j(hd - ib) - b \\
& = (e_0 jd)h - b(je_0 i + 1) \\
& = (e_0 jd)h - jb(e_0 i + j) \\
& = (e_0 jd)h - jb(h f_0) \\
& = hj(e_0 d - f_0)
\end{aligned}\end{equation}\tag{15}\label{eq15A}$$
where \eqref{eq8A} is used in the second last step. Thus, substituting this into \eqref{eq14A} and dividing by the common factor of $h$ gives
$$(g)n = (m)k + j(e_0 d - f_0) \tag{16}\label{eq16A}$$
Next, let
$$q = \gcd(g,m) \implies g = qr, m = qs, \gcd(r,s) = 1 \tag{17}\label{eq17A}$$
This also requires that $q \mid e_0 d - f_0$. If not, then let $p$ be a prime where $p \mid q$ but $p \not\mid e_0 d - f_0$. Consider if changing $e_0$ and $f_0$ will fix this. Let $e_0 = e_1 + k_1 h$ and $f_0 = f_1 + k_1 i$ where $e_1$ and $f_1$ also satisfy \eqref{eq8A} and $k_1$ is any integer. Then $e_0 d - f_0 = (e_1 + k_1 h)d - (f_1 + k_1 i) = e_1 d - f_1 + k_1(hd - i)$. If $p \mid e_1 d - f_1$, you can have $k_1$ be any multiple of $p$. Otherwise, as long as $p \not\mid hd - i$, you can choose a $k_1$ so the result is a multiple of $p$. This is a limitation which needs to be accounted for, with possibly changing the value of $m$ used initially helping in some cases. I'll leave this to you to check on & finish.
Otherwise, with $q \mid e_0 d - f_0$, you then have
$$e_0 d - f_0 = uq \tag{18}\label{eq18A}$$
Substituting \eqref{eq17A} and \eqref{eq18A} into \eqref{eq16A}, dividing by the common factor of $q$ and rearranging gives
$$rn - sk = u \tag{19}\label{eq19A}$$
Since $\gcd(r,s) = 1$, Bézout's lemma guarantees there's a solution, actually an infinite # of them, for $n_0$ and $k_0$ in
$$rn_0 + s(-k_0) = 1 \tag{20}\label{eq20A}$$
Thus, multiplying both sides by $u$ comparing to \eqref{eq19A} shows there's an infinite # of $n = un_0$ and $k = uk_0$.
In this solution, the only required condition on $|ad - bc|$ for there to be an infinite # of $n$, apart from any extra conditions from the limitation described in the paragraph between \eqref{eq17A} and \eqref{eq18A}, is that given in \eqref{eq5B}.
