4 votos

Raíces extrañas al resolver una ecuación cuadrática modular (congruencia)

\begin{gather} \frac{N^2+N}{2} \equiv 0 \pmod 4 \\ N^2+N\equiv 0\\ (N+\frac{1}{2})^2-\frac{1}{4}\equiv 0\\ 4(N+\frac{1}{2})^2-1\equiv 0\\ 2^2(N+\frac{1}{2})^2\equiv 1\\ (2N+1)^2\equiv 1 \\ 2N+1 \equiv 1\\ 2N=0\\ N=2,4,6,8...\\ 2N+1 \equiv 3\\ 2N=2\\ N=1,3,5,7...\\ \end{gather} En otras palabras, he demostrado $\forall N >0 \to \frac{N^2+N}{2} \equiv 0 \pmod 4$, lo cual es falso por ejemplo para $N=3$, $\frac{N^2+N}{2}$ tiene un residuo de 2

También me gustaría una solución correcta. Gracias.

6voto

David HAust Puntos 2696

Tu primer error es que escalaste por $\,2,\,$ lo que no es invertible $\!\bmod 4,\,$ por lo que esto no dará una congruencia equivalente. En cambio, da condiciones necesarias pero no suficientes sobre las raíces (por lo que posiblemente haya raíces extravagantes). Mira aquí para más información sobre la insuficiencia de inferencias unidireccionales.

Para obtener una congruencia equivalente necesitamos escalar también el módulo, ya que $\,4\mid a/2\iff 8\mid a,\,$ entonces

$$(n^2+n)/2\equiv 0\!\!\!\pmod{4}\iff n^2+n\equiv 0\!\!\!\pmod{8}\qquad$$

Ahora podemos completar el cuadrado como hiciste, pero dado que esto también implica escalar el módulo, esto terminará siendo infructuoso, llevándonos de vuelta a donde empezamos, es decir

$$\begin{align} n^2+n&\equiv 0\pmod{8}\\ \iff\ \ \ \ \ \ \ 4n^2+4n&\equiv 0\pmod{32}\\ \iff 4n^2+4n+1&\equiv 1\pmod{32}\\ \iff \ \ \ \ \ \, \color{#c00}{(2n+1)^2}&\:\color{#c00}{\equiv 1}\pmod{32}\\ \iff (2n)(2n+2)&\equiv 0\pmod{32}\\ \iff\ \ \ \ \ \ \ n(n+1)&\equiv 0\pmod{8} \end{align}\qquad$$

donde resolvimos $\,\color{#c00}{a^2\equiv 1}\,$ factorizando la diferencia de cuadrados $\,0\equiv a^2-1\equiv (a-1)(a+1).\,$ No puedes simplemente tomar raíces cuadradas como lo hiciste, por ejemplo $\,x^2\equiv 1\pmod{8}\,$ tiene $4$ raíces $\,x\equiv 1,3,5,7$.

En cambio, al ser $\,n,\,n\!+\!1\,$ coprimos, $\,8\mid n(n\!+\!1)\iff 8\mid n\,$ o $\,8\mid n\!+\!1,\,$ concluimos que $\,n(n+1)/2\equiv 0\pmod{4}\iff n\equiv 0,7\pmod{8}$

Finalmente, ten en cuenta que las fracciones modulares están bien definidas (existen de forma única) solo cuando son escribibles con un denominador coprimo al módulo, cuando $\,a/b := ab^{-1}.\,$ Para más información sobre las fracciones modulares, mira aquí y aquí.

3voto

John Omielan Puntos 431

Lo que hiciste incorrectamente está básicamente explicado en la respuesta de Peter, y en varios comentarios de la pregunta. Sin embargo, hay un problema más general al manipular congruencias, ya que estás tratando con enteros, que implica "fracciones" de la forma $\frac{p}{q}$ donde $\gcd(p,q) = 1$, lo cual realmente significa que la división por $q$ es multiplicar por su inverso multiplicativo módulo, es decir, $q^{-1}$. Sin embargo, solo los enteros que son primos relativos al módulo tienen inversos. Dado que $\gcd(4, 4) = 4 \neq 1$ y $\gcd(4, 2) = 2 \neq 1$, ni $2$ ni $4$ tienen un inverso en módulo $4$, por lo que mientras trabajas en ese módulo no puedes, en general, simplemente "dividir" por ninguno de esos valores, por ejemplo, $\frac{1}{2}$ y $\frac{1}{4}$ no tienen sentido.

En cuanto a cómo resolver correctamente tu ecuación de congruencia, nota que para cualquier solución $N$, hay algún número entero $j$ donde

$$\begin{equation}\begin{aligned} & \frac{N^2 + N}{2} \equiv 0 \pmod{4} \iff \frac{N^2 + N}{2} = 4j \iff \\ & N^2 + N = 8j \iff N^2 + N \equiv 0 \pmod{8} \end{aligned}\end{equation}\tag{1}\label{eq1A}$$

Debido a que $N$ y $N + 1$ son primos relativos entre sí, con uno siendo impar y el otro par, y dado que $8 = 2^3$ solo tiene factores primos de $2$, esto lleva a

$$\begin{equation}\begin{aligned} & N(N + 1) \equiv 0 \pmod{8} \implies \\ & (N \equiv 0 \pmod{8}) \lor (N + 1 \equiv 0 \pmod{8}) \implies \\ & N \equiv 0, 7 \pmod{8} \end{aligned}\end{equation}\tag{2}\label{eq2A}$$

Esto significa que los valores permitidos para $N$ son $N = 8k$ y $N = 8k + 7$ para cualquier $k \in \mathbb{Z}$.

0voto

Peter Puntos 86

En aritmética módulo $4$, no puedes dividir por $4$ o $2$. Es como dividir por $0$ en aritmética normal; puedes escribir la expresión pero no hay un número que sea igual a ella.

Si divides y multiplicas por cero puedes probar que todos los números son iguales. Esto es por supuesto inconsistente con nuestra aritmética normal, y también con la aritmética modular. La razón es que no puedes dividir por cero.

Si permites la división por cero obtienes la aritmética poco interesante donde solo hay un número.

Nota que la segunda línea es una ecuación legal, y sus soluciones, mediante prueba y error, son $3$ y $4$.

Tu ejemplo es interesante en la forma en que disfraza el $0$ como $4$, y también como $2$, ya que $2=\sqrt{4}=\sqrt{0}=0$.

No había visto un ejemplo como este utilizando aritmética modular.

-1voto

Eugen Puntos 121

$(2N+1)^{2} \equiv 1 $

$2N+1 \equiv 1$

Este paso está mal, por ejemplo: $(2*3+1)^2 \equiv 1$.

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X