3.1: Introducción a las congruencias

Como mencionamos en la introducción, la teoría de las congruencias fue desarrollada por Gauss a principios del siglo XIX.

Dejar\(m\) ser un entero positivo. Decimos que\(a\) es congruente con\(b\) modulo\(m\) si\(m \mid (a-b)\) donde\(a\) y\(b\) son enteros, es decir, si\(a=b+km\) donde\(k\in \mathbb{Z}\).

Si\(a\) es congruente con\(b\) módulo\(m\), escribimos\(a\equiv b(mod\ m)\).

\(19\equiv 5 (mod \ 7)\). Del mismo modo\(2k+1 \equiv 1 (mod\ 2)\) lo que significa que cada número impar es congruente con 1 módulo 2.

Hay muchas propiedades comunes entre ecuaciones y congruencias. Algunas propiedades se enumeran en el siguiente teorema.

Teorema: Propiedades de las Congruencias

Dejar\(a, b, c\) y\(d\) denotar enteros. Dejar\(m\) ser un número entero positivo. Entonces:

1. Si\(a \equiv b(mod \ m)\), entonces\(b\equiv a (mod \ m)\).
2. Si\(a\equiv b(mod \ m)\) y\(b\equiv c(mod \ m)\), entonces\(a\equiv c (mod \ m)\).
3. Si\(a\equiv b(mod\ m)\), entonces\(a+c \equiv b+c (mod \ m)\).
4. Si\(a\equiv b(mod\ m)\), entonces\(a-c \equiv b-c (mod \ m)\).
5. Si\(a\equiv b(mod\ m)\), entonces\(ac \equiv bc (mod \ m)\).
6. Si\(a\equiv b(mod\ m)\), entonces\(ac \equiv bc (mod \ mc)\), para\(c>0\).
7. Si\(a\equiv b(mod\ m)\) y\(c \equiv d (mod \ m)\) entonces\(a+c \equiv (b+d) (mod \ m)\).
8. Si\(a\equiv b(mod\ m)\) y\(c \equiv d (mod \ m)\) entonces\(a-c \equiv (b-d) (mod \ m)\).
9. Si\(a\equiv b(mod\ m)\) y\(c \equiv d (mod \ m)\) entonces\(ac \equiv bd (mod \ m)\).

1. Si\(a \equiv b(mod \ m)\), entonces\(m\mid (a-b)\). Así existe entero\(k\) tal que\(a-b=mk\), esto implica\(b-a=m(-k)\) y así\(m\mid (b-a)\). En consecuencia\(b\equiv a (mod \ m)\).
2. Desde\(a\equiv b(mod \ m)\) entonces\(m\mid (a-b)\). También,\(b\equiv c(mod \ m)\), entonces\(m\mid (b-c)\). En consecuencia, ahí salen dos enteros\(k\) y\(l\) tal que\(a=b+mk\) y\(b=c+ml\), lo que implica que\(a=c+m(k+l)\) dando eso\(a=c (mod \ m)\).
3. Desde\(a\equiv b (mod \ m)\) entonces\(m \mid (a-b)\). Entonces si sumamos y\(c\) restamos obtenemos\[m\mid ((a+c)-(b+c))\] y como resultado\[a+c\equiv b+c (mod \ m).\]
4. Desde\(a\equiv b (mod \ m)\) entonces\(m \mid (a-b)\) así podemos restar y sumar\(c\) y conseguimos\[m\mid ((a-c)-(b-c))\] y como resultado\[a-c\equiv b-c (mod \ m).\]
5. Si\(a \equiv b(mod \ m)\), entonces\(m\mid (a-b)\). Así existe entero\(k\) tal que\(a-b=mk\) y como resultado\(ac-bc=m(kc)\). Así\[m\mid (ac-bc)\] y por lo tanto\[ac\equiv bc (mod \ m).\]
6. Si\(a \equiv b(mod \ m)\), entonces\(m\mid (a-b)\). Así existe entero\(k\) tal que\(a-b=mk\) y como resultado\[ac-bc=mc(k).\] Así\[mc\mid (ac-bc)\] y por lo tanto\[ac\equiv bc (mod \ mc).\]
7. Desde\(a\equiv b(mod \ m)\) entonces\(m\mid (a-b)\). También,\(c\equiv d(mod \ m)\), entonces\(m\mid (c-d)\). Como resultado, ahí salen dos enteros\(k\) y\(l\) tal que\(a-b=mk\) y\(c-d=ml\). Tenga en cuenta que\[(a-b)+(c-d)=(a+c)-(b+d)=m(k+l).\] Como resultado, de\[m\mid ((a+c)-(b+d)),\] ahí\[a+c\equiv b+d(mod \ m).\]
8. Si\(a=b+mk\) y\(c=d+ml\) donde\(k\) y\(l\) son enteros, entonces\[(a-b)-(c-d)=(a-c)-(b-d)=m(k-l).\] Como resultado,\[m\mid ((a-c)-(b-d)),\] por lo tanto\[a-c\equiv b-d(mod \ m).\]
9. Ahí salen dos enteros\(k\) y\(l\) tal que\(a-b=mk\) y\(c-d=ml\) y así\(ca-cb=m(ck)\) y\(bc-bd=m(bl)\). Tenga en cuenta que\[(ca-cb)+(bc-bd)=ac-bd=m(kc-lb).\] Como resultado, de\[m\mid (ac-bd),\] ahí\[ac\equiv bd(mod \ m).\]

1. Porque\(14\equiv 8(mod\ 6)\) entonces\(8 \equiv 14 (mod\ 6)\).
2. Porque\(22\equiv 10(mod \ 6)\) y\(10 \equiv 4(mod \ 6)\). Observe eso\(22\equiv 4(mod \ 6)\).
3. Porque\(50\equiv 20 (mod\ 15)\), entonces\(50+5=55\equiv 20+5=25(mod\ 15)\).
4. Porque\(50\equiv 20 (mod\ 15)\), entonces\(50-5=45\equiv 20-5=15(mod\ 15)\).
5. Porque\(19\equiv 16(mod3)\), entonces\(2(19)=38\equiv 2(16)=32(mod \ 3).\)
6. Porque\(19\equiv 16(mod3)\), entonces\(2(19)=38\equiv 2(16)=32(mod \ 2(3)=6).\)
7. Porque\(19\equiv 3 (mod \ 8)\) y\(17\equiv 9(mod \ 8)\), entonces\(19+17=36\equiv 3+9=12(mod \ 8)\).
8. Porque\(19\equiv 3 (mod \ 8)\) y\(17\equiv 9(mod \ 8)\), entonces\(19-17=2\equiv 3-9=-6(mod \ 8)\).
9. Porque\(19\equiv 3 (mod \ 8)\) y\(17\equiv 9(mod \ 8)\), entonces\(19(17)=323\equiv 3(9)=27(mod \ 8)\).

Presentamos ahora un teorema que mostrará una diferencia entre ecuaciones y congruencias. En las ecuaciones, si dividimos ambos lados de la ecuación por un número distinto de cero, la igualdad se mantiene. Si bien en congruencias, no es necesariamente cierto. En otras palabras, dividir ambos lados de la congruencia por el mismo entero no preserva la congruencia.

1. Si\(a,b, c\) y\(m\) son enteros tales que\(m>0\),\(d=(m,c)\) y\(ac\equiv bc(mod \ m)\), entonces\(a\equiv b (mod \ m/d)\).
2. Si\((m,c)=1\) entonces\(a=b(mod \ m)\) si\(ac\equiv bc(mod \ m)\).

La Parte 2 sigue inmediatamente de la Parte 1. Para la Parte 1, si\(ac\equiv bc(mod \ m)\), entonces de\[m\mid (ac-bc)=c(a-b).\] ahí existe\(k\) tal que\(c(a-b)=mk\). Dividiendo ambos lados por\(d\), obtenemos\((c/d)(a-b)=k(m/d)\). Ya que\((m/d,c/d)=1\), se deduce que\(m/d \mid (a-b)\). De ahí\(a\equiv b (mod \ m/d)\).

\(38 \equiv 10 (mod\ 7)\). Desde\((2,7)=1\) entonces\(19\equiv 5 (mod \ 7).\)

El siguiente teorema combina varias congruencias de dos números con diferentes módulos.

Si\[a\equiv b(mod \ m_1), a\equiv b(mod \ m_2),...,a\equiv b(mod \ m_t)\] donde\(a,b,m_1,m_2,...,m_t\) son enteros y\(m_1,m_2,...,m_t\) son positivos, entonces\[a\equiv b(mod \ \langle m_1,m_2,...m_t\rangle)\]

Ya que\(a\equiv b (mod \ m_i)\) para todos\(1\leq i\leq t\). Por lo tanto\(m_i \mid (a-b)\). En consecuencia,\[\langle m_1,m_2,...,m_t\rangle \mid (a-b)\] (probar esto como un ejercicio). Por lo tanto\[a\equiv b(mod \ \langle m_1,m_2,...m_t\rangle).\]

Ejercicios

1. Determinar si 3 y 99 son congruentes módulo 7 o no.
2. Mostrar que si\(x\) es un número entero impar, entonces\(x^2\equiv 1(mod \ 8)\)
3. Demostrar que si\(a,b, m\) y\(n\) son enteros tales que\(m\) y\(n\) son positivos,\(n \mid m\) y\(a\equiv b (mod \ m)\), entonces\(a\equiv b (mod \ n).\)
4. Mostrar que si\(a_i\equiv b_i(mod \ m)\) para\(i=1,2,...,n\), donde\(m\) es un entero positivo y\(a_i,b_i\) son enteros para\(j=1,2,...,n\), entonces\(\sum_{i=1}^na_i\equiv \sum_{i=1}^nb_i(mod \ m)\)
5. Para lo\(n\) cual\(1+2+...+(n-1)\equiv 0(mod \ n)\) sostiene la expresión.

Colaboradores y Atribuciones

• Template:ContribRaji