Cálculo de la intersección de dos secuencias aritméticas $(a\mathbb{Z} + b) \cap (c \mathbb{Z} + d)$

Question

Me estoy atascando escribiendo una fórmula general para la intersección de dos secuencias aritméticas.

$$ (a\mathbb{Z} + b) \cap (c \mathbb{Z} + d) = \begin{cases} \varnothing & \text{if ???} \\ ?\mathbb{Z} + ? & \text{otherwise}\end{cases} $$

Para dos secuencias aritméticas cualesquiera, sabría calcular su intersección (posiblemente nula), pero no sé cómo escribir una fórmula en general.

Answer 1

Efectivamente, estás pidiendo soluciones a la ecuación: $$aX - c Y = d -b$$ esto tiene solución si y sólo si $\gcd(a,c)\mid d-b$ . Si tiene solución puedes encontrarla utilizando el Algoritmo Euclidiano.

Una vez que tenga una solución $(x_0,y_0)$ , entonces la intersección es $(ax_0 + b)+ \operatorname{lcm}(a,c) \mathbb{Z}$ .

No hay una manera muy directa de "escribir" una solución $(x_0,y_0)$ pero usando inversiones modulares podrías acercarte.

Answer 2

Esto es como resolver la ecuación diofantina $$ax+b=cy+d$$ que es $$ax-cy=d-b$$

Esta ecuación tiene solución si y sólo si $\gcd(a,c)$ divide $d-b$ . Si esta condición se cumple, hay infinitas soluciones. La intersección de las progresiones aritméticas es vacía o infinita, y si es infinita también es una progresión aritmética.

Ver este .

Answer 3

Dos secuencias aritméticas $a\mathbb{Z}+b$ et $c\mathbb{Z}+d$ con $a,b,c,d\in\mathbb{Z}$ tal que $a\neq 0$ et $c\neq 0$ se cruzan de forma no trivial si y sólo si $\gcd(a,c)$ divide $b-d$ , en cuyo caso $$(a\mathbb{Z}+b)\cap(c\mathbb{Z}+d)=\text{lcm}(a,c)\mathbb{Z}+r\,,$$ donde $r$ es la única solución módulo $\text{lcm}(a,c)$ al sistema de congruencia $r\equiv b\pmod{a}$ et $r\equiv d\pmod{c}$ . Para ser justos, esto es precisamente una reformulación del Teorema Chino del Resto.

Para demostrar la primera afirmación, dejemos que $t:=\gcd(a,c)$ . Si $(a\mathbb{Z}+b)\cap (c\mathbb{Z}+d)\neq \emptyset$ entonces supongamos que $s$ está en la intersección. Por lo tanto, $ax+b=s=cy+d$ para algunos $x,y\in\mathbb{Z}$ . Así, $-ax+cy=b-d$ Así que $t\mid (b-d)$ , como $t\mid a$ et $t\mid c$ . A la inversa, supongamos que $t\mid b-d$ . Entonces, existe $x,y\in\mathbb{Z}$ tal que $b-d=-ax+cy$ Así que $ax+b=cy+d$ . Por lo tanto, $a\mathbb{Z}+b$ et $c\mathbb{Z}+d$ tienen un elemento común.

Ahora, demostraremos la segunda afirmación. Sea $m:=\text{lcm}(a,c)$ . Evidentemente, cada elemento de $P:=(a\mathbb{Z}+b)\cap(c\mathbb{Z}+d)$ es congruente con $r$ modulo $m$ por el Teorema del Resto Chino. Afirmamos que todo número de este tipo está efectivamente en $P$ . Sea $k\in\mathbb{Z}$ . Desde $r\equiv b\pmod{a}$ et $r\equiv d\pmod{c}$ tenemos $r=ax+b$ et $r=cy+d$ para algunos $x,y\in\mathbb{Z}$ . Ahora, $km+r=a\left(x+k\frac{m}{a}\right)+b$ et $km+r=c\left(y+k\frac{m}{c}\right)+d$ con $x+k\frac{m}{a},y+k\frac{m}{c}\in\mathbb{Z}$ . Por lo tanto, $km+r\in P$ y la conclusión es la siguiente.

Answer 4

Equivale a resolver el sistema de congruencias simultáneas: $$\begin{cases} x\equiv b\mod a\\x\equiv d\mod c \end{cases}$$ Este sistema tiene una solución idf y sólo si $b\equiv d\mod \gcd(a,c)$ y es único módulo $\operatorname{lcm}(a,c)$ .