Entender por qué es válida la expansión monovariable de la aritmética modular.

Question

Estaba leyendo: https://arxiv.org/pdf/1206.5114.pdf página 10 y me encontré con un teorema impar.

Establece, que el sistema:

$$\begin{matrix} 2x_1+ 3x_2 \equiv 1 \mod 5 \\ 3x_1 + 5x_2 \equiv 1 \mod 7 \end{matrix}$$

Se puede "reescribir" como:

$$\begin{matrix} 2x_1+ 3x_2 +5x_3 = 1 \\ 3x_1 + 5x_2 + 7x_3 = 1 \end{matrix}$$

Ahora bien, ¿qué significa exactamente "reescribir aquí"? ¿Es que para cada solución en el primer sistema existe una solución en el segundo? ¿O que para cada solución en el segundo sistema existe una solución en el primero? ¿O ambas cosas?

Al menos la noción de "AMBOS" me parece imposible. Por la sencilla razón de que si dejamos que $X = 2x_1 + 3x_2$ y que $Y = 3x_1 + 5x_2$

Entonces estamos afirmando que si

$$X \equiv 1 \mod 5$$ $$Y \equiv 1 \mod 7$$

Que existe un $x_3$ tal que

$$X + 5x_3 = 1$$ $$Y + 7x_3 = 1$$

Ahora bien, a mí esto me parece muy impar, ya que si analizamos

$$X \equiv 1 \mod 5$$

Para mí todo lo que dice es que hay ALGÚN entero $s$ tal que $X = 5s + 1$ y del mismo modo existe ALGÚN número entero $r$ tal que $Y = 7r + 1$ . La idea de que $s = r$ es necesario parece descaradamente falso (pongamos X = 11, Y = 8 como contraejemplo). Con AMBOS descartados, (y nuestro contraejemplo descartando que toda solución del primer sistema implica una solución del segundo sistema) está bastante claro que, en el mejor de los casos, toda solución del segundo sistema es una solución del primero.

Yo diría que se trata de una grave pérdida de información y no de una simple "reescritura", así que ¿se trata de un error del artículo y pretendían comunicar otra cosa? o ¿me estoy perdiendo algún detalle importante? o ¿es correcto el análisis hasta aquí y el término "reescrito" implica una pérdida oculta de información que el artículo no aclara?

Answer 1

Las soluciones a $$2x_1+3x_2+5x_3=1, 3x_1+5x_2+7x_3=1$$ satisfacer $$2x_1+3x_2≡1, \mod5$$

$$3x_1+5x_2≡1, \mod7$$

Pero las soluciones al segundo sistema no son necesariamente soluciones al primer sistema porque puede que tengas $$2x_1+3x_2+5x_3=1, 3x_1+5x_2+7x_4=1$$ donde $x_3\ne x_4$

Answer 2

Ahora bien, ¿qué se entiende exactamente por "reescribir aquí"?

Las expresiones son equivalentes. Para un ejemplo más simple, considere:

$$4x_1 + 3x_2 \equiv 5 \pmod 6 \tag 1$$

Escribiré esta expresión de forma similar a ese archivo PDF. Considera la definición de congruencia en este contexto:

$$a \equiv b \pmod m \iff \frac{a-b}{m} = k \in \mathbb Z$$

Entonces $(1)$ se convierte en

$$4x_1 + 3x_2 \equiv 5 \pmod 6 \iff \frac{4x_1 + 3x_2 - 5}{6} = k \in \mathbb{Z} \tag 2$$

Multiplicar por $6$ a cada lado en $(3)$ Añadir $5$ a cada lado, y restar el entero $k$ de cada uno para obtener

$$\frac{4x_1 + 3x_2 - 5}{6} = x_3 \in \mathbb{Z} \iff 4x_1 + 3x_2 -6k = 5 \tag 4$$

Desde $k \in \mathbb{Z}$ conocemos un número entero $-k$ existe. Podemos tomar $k = -x_3$ para algunos números enteros $x_3$ y así $(4)$ se convierte en

$$4x_1 + 3x_2 -6k = 5 \iff 4x_1 + 3x_2 -6(-x_3) = 5 \iff 4x_1 + 3x_2 + 6x_3 = 5$$

---

Ahora, por supuesto, lo anterior es algo de lo que creo que ya eres consciente de alguna forma, y que tocas. Así que voy a abordar otro punto:

A mí esto me parece $$X \equiv 1 \mod 5$$ Para mí todo lo que dice es que hay ALGÚN entero $s$ tal que $X = 5s + 1$ [...]

Si bien esto es algo así como cierto, soluciones $X$ a una congruencia modular como la anterior son en realidad una clase de equivalencia de enteros. El "algún entero" al que te refieres es probablemente el "menor residuo" (al menos, eso es lo que a menudo me parece que la gente malinterpreta como), pero en esta ecuación anterior hay múltiples soluciones porque, por nuestra definición de congruencia modular,

$$X \equiv 1 \pmod 5 \iff \frac{X-1}{5} = k \in \mathbb{Z}$$

O, de manera menos formal, soluciones $X$ tienen un resto $1$ cuando se divide por $5$ (no es la mejor definición, pero a veces resulta engañoso verlo así). Entonces, ¿qué $X$ ¿son una solución?

$$X = \{ ..., -9, -4, 1, 6, 9, ... \} = \{ k \in \mathbb{Z} | k = 5n, n \in \mathbb{Z} \}$$

Se trata de una clase de equivalencia de soluciones, que denotamos por $[1]$ (ya que $1$ es el menor residuo). Todas son soluciones de la congruencia.

Al extrapolar esta lógica a un sistema de congruencias, piense en él como en un sistema ordinario de ecuaciones. Muchas entradas podrían satisfacer cualquiera de las ecuaciones (no necesariamente una), y el sistema sólo busca las que satisfacen todas las ecuaciones (siempre que existan). Aquí se aplica una idea similar.