Consideremos para algunos enteros positivos $a$ , $b$ , $c$ y $d$ que hay un $m \gt 1$ tal que
$$m = \gcd(an + b, cn + d) \tag{1}\label{eq1A}$$
para al menos un número entero $n$ . Así, para algunos enteros $e$ y $f$ con $\gcd(e,f) = 1$ , se obtiene
$$an + b = em \tag{2}\label{eq2A}$$
$$cn + d = fm \tag{3}\label{eq3A}$$
Siguiente, $a$ veces \eqref {eq3A} menos $c$ veces \eqref {ec2A} da
$$ad - bc = (af - ec)m \tag{4}\label{eq4A}$$
Esto muestra $m \mid ad - bc$ . Si $ad - bc = 0$ , entonces para $m \gt 1$ , usted tiene $af - ec = 0 \implies af = ec$ . Desde $\gcd(e,f) = 1$ entonces $e \mid a$ y $f \mid c$ . Desde $a$ y $c$ son números enteros fijos, sólo hay un número finito de valores posibles para $e$ y $f$ por lo que no puede haber un número infinito de $n$ .
A partir de este momento, asuma $ad - bc \neq 0$ . A continuación, dejemos que
$$g = \gcd(a,c) \implies a = gh, c = gi, \gcd(h,i) = 1 \tag{5}\label{eq5A}$$
Nota $af - ec$ debe ser un múltiplo integral de $g$ Así que $m \mid \frac{ad - bc}{\gcd(a,c)} = hd - ib$ . Así, $m \gt 1$ requiere $|ad - bc| \gt \gcd(a,c) = g$ . Supongamos que esto es cierto, es decir, una condición necesaria es que
$$\frac{|ad - bc|}{\gcd(a,c)} \gt 1 \tag{5B}\label{eq5B}$$
También tienen
$$m = |hd - ib| \tag{6}\label{eq6A}$$
A continuación, haz que
$$j = \text{sgn}(ad - bc) \tag{7}\label{eq7A}$$
donde $\text{sgn}$ es el Función del signo , lo que significa que es $1$ si el argumento es positivo, $0$ si es $0$ Si no, su $-1$ si es negativo. Desde \eqref {eq4A}, \eqref {eq5A}, \eqref {eq6A} y \eqref {eq7A} se obtiene
$$hf - ei = j \tag{8}\label{eq8A}$$
Desde $\gcd(h,i) = 1$ , La identidad de Bézout garantiza que hay una solución, siendo el conjunto de soluciones
$$e = e_0 + kh \tag{9}\label{eq9A}$$
$$f = f_0 + ki \tag{10}\label{eq10A}$$
para algunos enteros fijos $e_0$ y $f_0$ y $k$ siendo un número entero cualquiera. Obsérvese la sustitución de \eqref {eq9A} y \eqref {eq10A} en \eqref {eq2A} y \eqref {eq3A} resulta en $2$ ecuaciones lineales en el $2$ incógnitas de $k$ y $n$ . Si el $2$ fueran linealmente independientes, se obtendría una sola solución para $k$ y $n$ . Así, un número infinito de valores de $n$ requiere la $2$ ecuaciones para ser depende linealmente es decir, uno es múltiplo del otro. Para comprobarlo, sustituye \eqref {eq5A}, \eqref {eq9A} y \eqref {eq10A} en \eqref {eq2A} y \eqref {eq3A}, mover los términos del lado derecho a la izquierda, y reunir los términos que implican $n$ y $k$ juntos para conseguir
$$(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}$$
Como se puede ver, la multiplicación de \eqref {eq11A} por $i$ y \eqref {ecuación 12A} por $h$ provoca la primera $2$ términos sean iguales. Por lo tanto, también se requiere (donde \eqref {eq8A} se utiliza a continuación) que
$$\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}$$
Esto coincide con \eqref {eq6A}, por lo que no hay ningún requisito adicional para \eqref {eq2A} y \eqref {eq3A} sean múltiplos entre sí. Por lo tanto, basta con utilizar la versión actualizada de \eqref {eq2A} en \eqref {eq11A} para obtener
$$(gh)n = (hm)k + (e_0 m - b) \tag{14}\label{eq14A}$$
Desde \eqref {eq6A} y \eqref {eq7A}, tienes $m = j(hd - ib)$ Esto significa que
$$\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}$$
donde \eqref {eq8A} se utiliza en el penúltimo paso. Así, sustituyendo esto en \eqref {eq14A} y dividiendo por el factor común de $h$ da
$$(g)n = (m)k + j(e_0 d - f_0) \tag{16}\label{eq16A}$$
A continuación, dejemos que
$$q = \gcd(g,m) \implies g = qr, m = qs, \gcd(r,s) = 1 \tag{17}\label{eq17A}$$
Esto también requiere que $q \mid e_0 d - f_0$ . Si no es así, entonces que $p$ sea un primo donde $p \mid q$ pero $p \not\mid e_0 d - f_0$ . Considere si el cambio de $e_0$ y $f_0$ arreglará esto. Deja que $e_0 = e_1 + k_1 h$ y $f_0 = f_1 + k_1 i$ donde $e_1$ y $f_1$ también satisfacen \eqref {eq8A} y $k_1$ es un número entero cualquiera. Entonces $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)$ . Si $p \mid e_1 d - f_1$ , puedes tener $k_1$ sea cualquier múltiplo de $p$ . Por lo demás, siempre que $p \not\mid hd - i$ puede elegir un $k_1$ por lo que el resultado es un múltiplo de $p$ . Esta es una limitación que hay que tener en cuenta, con la posible modificación del valor de $m$ utilizado inicialmente ayudando en algunos casos. Te dejo esto para que lo compruebes y lo termines.
De lo contrario, con $q \mid e_0 d - f_0$ Entonces, usted tiene
$$e_0 d - f_0 = uq \tag{18}\label{eq18A}$$
Sustituyendo \eqref {eq17A} y \eqref {eq18A} en \eqref {eq16A}, dividiendo por el factor común de $q$ y reordenando da
$$rn - sk = u \tag{19}\label{eq19A}$$
Desde $\gcd(r,s) = 1$ el lema de Bézout garantiza que hay una solución, en realidad un número infinito de ellas, para $n_0$ y $k_0$ en
$$rn_0 + s(-k_0) = 1 \tag{20}\label{eq20A}$$
Así, multiplicando ambos lados por $u$ comparando con \eqref {eq19A} muestra que hay un número infinito de $n = un_0$ y $k = uk_0$ .
En esta solución, la única condición requerida en $|ad - bc|$ para que haya un número infinito de $n$ Además de cualquier condición adicional de la limitación descrita en el párrafo entre \eqref {eq17A} y \eqref {eq18A}, es la dada en \eqref {eq5B}.
