1.17: Congruencias
- Page ID
- 117395
Vamos\(m\ge0\). Escribimos\(a\equiv b\pmod m\) si\(m\mid (a-b)\), y decimos que\(a\) es congruente con\(b\) modulo\(m\). Aquí\(m\) se dice que es el módulo de la congruencia. La notación\(a\not\equiv b\pmod m\) significa que es falso eso\(a\equiv b\pmod m\).
- \(25\equiv 1\pmod 4\)desde\(4\mid 24\)
- \(25\not\equiv 2\pmod 4\)desde\(4\nmid 23\)
- \(1\equiv -3\pmod 4\)desde\(4\mid 4\)
- \(a\equiv b\pmod 1\)para todos\(a\),\(b\) ya que “\(1\)divide todo”.
- \(a \equiv b \pmod 0 \Longleftrightarrow a = b\)para todos\(a\),\(b\) ya que “sólo\(0\) divide”\(0\).
Como ve, los casos\(m=1\) y no\(m=0\) son muy interesantes por lo que en su mayoría solo nos interesará el caso\(m\ge 2\).
No confundas el uso de mod en Definición\(\PageIndex{1}\) con el de Definición 1.5.3. Veremos que los dos usos del mod están relacionados, pero tienen diferentes significados: Recordar
\[\boxed{\begin{array}{l}a\pmod b=r\text{ where }r\text{ is the remainder given by }\\ \text{the Division Algorithm when }a\text{ is divided by }b,\end{array}}\nonumber\]
y por definición\(\PageIndex{1}\)\[\boxed{a\equiv b\pmod m\text{ means }m\mid (a-b).}\nonumber \]
El enunciado\[25\equiv 5\pmod 4\text{ is true}\, ,\nonumber \] desde\(4\mid 20\) pero\[25=5\bmod 4\text{ is false}\, ,\nonumber \] desde este último significa\(25=1\).
El mod in\(a\equiv b\pmod m\) es, junto con el\(\equiv\), parte de una relación binaria, mientras que el mod in\(a \bmod b\) es una operación binaria.
Más terminología:
Expresiones como\[\begin{aligned} x &=2 \\ 4^2 &=16 \\ x^2+2x &=\sin(x)+3\end{aligned}\] son ecuaciones. Por analogía, expresiones como\[\begin{aligned} x &\equiv 2\pmod{16} \\ 25 &\equiv 5\pmod 5 \\ x^3+2x &\equiv 6x^2+3\pmod{27}\end{aligned}\] se llaman congruencias. Antes de discutir más a fondo la analogía entre ecuaciones y congruencias, mostramos la relación entre las dos definiciones diferentes de mod.
Para\(m>0\) y para todos\(a\)\(b\):\[a \equiv b \pmod m \Longleftrightarrow a \bmod m= b \bmod m.\nonumber \]
Prueba
“\(\Rightarrow\)” Supongamos que\(a\equiv b\pmod m\). Dejar\(r_1=a\bmod m\) y\(r_2=b\bmod m\). Eso queremos demostrarlo\(r_1=r_2\). Por definición tenemos
- \(m\mid (a-b)\),
- \(a=mq_1+r_1\),\(0\le r_1<m\), y
- \(b=mq_2+r_2\),\(0\le r_2<m\).
De (1) obtenemos\[a-b=mt\nonumber \] para algunos\(t\). De ahí\[a=mt+b.\nonumber \] usando (2) y (3) vemos que\[a=mq_1+r_1=m\left(q_2+t\right)+r_2.\nonumber \] Desde\(0\le r_1<m\) y\(0\le r_2<m\) por la parte de singularidad del Algoritmo de División obtenemos\(r_1=r_2\), según se desee.
“\(\Leftarrow\)” Supongamos que\(a\bmod m=b\bmod m\). Debemos demostrarlo\(a\equiv b\pmod m\). Si\(r=a\bmod m=b\bmod m\), entonces por definición tenemos\[a=mq_1+r,\quad 0\le r<m,\nonumber \] y\[b=mq_2+r,\quad 0\le r<m.\nonumber \] De ahí\[a-b=m\left(q_1-q_2\right).\nonumber \] Esto demuestra eso\(m\mid (a-b)\) y por lo tanto\(a\equiv b\pmod m\), como se desee.
Los dos teoremas siguientes muestran que las congruencias y ecuaciones comparten muchas propiedades similares.
Para todos\(a\)\(b\),,\(c\) y\(m>0\) tenemos
- \(a\equiv a\pmod m\)[reflexividad]
- \(a\equiv b\pmod m\Rightarrow b\equiv a\pmod m\)[simetría]
- \(a\equiv b\pmod m\)y\(b\equiv c\pmod m\Rightarrow a\equiv c\pmod m\) [transitividad]
Prueba
de (1) Ver Ejercicio\(\PageIndex{1}\).
de (2) Si\(a\equiv b\pmod m\), entonces\(m\mid (a-b)\). De ahí\(a-b=mq\). De ahí\(b-a=m(-q)\), así\(m\mid (b-a)\). De ahí\(b\equiv a\pmod m\).
de (3) Si\(a\equiv b\pmod m\) y\(b\equiv c\pmod m\) entonces\(m\mid (a-b)\) y\(m\mid (b-c)\). Por la propiedad de linealidad\(m\mid ((a-b)+(b-c))\). Es decir,\(m\mid (a-c)\). De ahí\(a\equiv c\pmod m\).
Recordemos que un polinomio es una expresión de la forma\[f(x)=a_nx^n+a_{n-1}x^{n-1}+\dotsb+a_1x+a_0.\nonumber \] Aquí asumiremos que los coeficientes\(a_n,\dotsc,a_0\) son enteros y\(x\) también representa una variable entera. Aquí, por supuesto,\(n\ge 0\) y\(n\) es un entero.
Si\(a\equiv b \pmod m\) y\(c\equiv d\pmod m\), entonces
- \(a\pm c\equiv b\pm d\pmod m\)
- \(ac\equiv bd\pmod m\)
- \(a^n\equiv b^n\pmod m\)para todos\(n\ge 1\)
- \(f(a)\equiv f(b) \pmod m\)para todos los polinomios\(f(x)\) con coeficientes enteros.
Prueba
de (1) Para probar (1) ya que\(a-c=a+(-c)\), basta con probar sólo el “\(+\)caso”. Por suposición\(m\mid (a-b)\) y\(m\mid (c-d)\). Por linealidad,\(m\mid ((a-b)+(c-d))\), es decir\(m\mid ((a+c)-(b+d))\). De ahí\[a+c\equiv b+d\pmod m.\nonumber \]
de (2) Desde\(m\mid (a-b)\) y\(m\mid (c-d)\) por linealidad,\[m\mid (c(a-b)+b(c-d)).\nonumber \] Ahora\(c(a-b)+b(c-d)=ca-bd\), de ahí\[m \mid (ca-bd),\nonumber \] y\(ca\equiv bd\pmod m\), como se desee.
de (3) Demostramos\(a^n\equiv b^n\pmod m\) por inducción sobre\(n\). Si\(n=1\), el resultado es cierto por nuestra suposición de que\(a\equiv b\pmod m\). Supongamos que se sostiene para\(n=k\). Entonces tenemos\(a^k\equiv b^k\pmod m\). Esto, junto con\(a\equiv b\pmod m\) el uso (2) anterior, da\(aa^k\equiv bb^k\pmod m\). De ahí\(a^{k+1}\equiv b^{k+1}\pmod m\). Entonces se sostiene para todos\(n\ge 1\), por el PMI.
de (4) Let\(f(x)=c_nx^n+\dotsb+c_1x+c_0\). Demostramos por inducción sobre\(n\) eso si\(a\equiv b\pmod m\) entonces\[c_na^n+\dotsb+c_0\equiv c_nb^n+\dotsb+c_0\pmod m.\nonumber \] Si\(n=0\) tenemos\(c_0\equiv c_0\pmod m\) por Teorema\(\PageIndex{2}\) (1). Supongamos que el resultado se mantiene para\(n=k\). Entonces tenemos\[\label{eq: thm 17-3 first} c_ka^k+\dotsb+c_1a+c_0\equiv c_kb^k+\dotsb+c_1b+c_0\pmod m.\] Por la parte (3) anterior tenemos\(a^{k+1}\equiv b^{k+1}\pmod m\). Ya que\(c_{k+1}\equiv c_{k+1}\pmod m\) usando (2) anterior tenemos\[\label{eq: thm 17-3 second} c_{k+1}a^{k+1}\equiv c_{k+1}b^{k+1}\pmod m.\] Ahora podemos aplicar el Teorema\(\PageIndex{3}\) (1) a las ecuaciones\(\eqref{eq: thm 17-3 first}\) y\(\eqref{eq: thm 17-3 second}\) para obtener\[c_{k+1}a^{k+1}+c_ka^k+\dotsb+c_0\equiv c_{k+1}b^{k+1}+c_kb^k+\dotsb+c_0\pmod m.\nonumber \] Así por el PMI, el resultado se mantiene para\(n\ge 0\).
Antes de continuar desarrollando propiedades de congruencias, damos el siguiente ejemplo para mostrar una manera en que las congruencias pueden ser útiles.
(Este ejemplo fue tomado de [1] Introducción a la Teoría Analítica de Números, de Tom Apostol.)
Los primeros cinco números de Fermat\[F_0=3,\quad F_1=5,\quad F_2=17,\quad F_3=257,\quad F_4=65,537\nonumber \] son primos. Mostramos usando congruencias sin calcular explícitamente\(F_5\) que\(F_5=2^{32}+1\) es divisible por\(641\) y por lo tanto no es primo: [apóstol]\[\begin{aligned} 2^2 &=4 \\ 2^4 &=\left(2^2\right)^2=4^2=16 \\ 2^8 &=\left(2^4\right)^2=16^2=256 \\ 2^{16} &=\left(2^8\right)^2=256^2=65,536\end{aligned}\]\[65,536\equiv 154\pmod{641}.\nonumber \] Así tenemos\[2^{16}\equiv 154\pmod{641}.\nonumber \] Por Teorema\(\PageIndex{3}\) (3): \[\left(2^{16}\right)^2\equiv (154)^2\pmod{641}.\nonumber \]Es decir,\[2^{32}\equiv 23,716\pmod{641}.\nonumber \] Desde\[23,716\equiv 640\pmod{641}\nonumber \] y\[640\equiv-1\pmod{641}\nonumber \] tenemos\[2^{32}\equiv-1\pmod{641}\nonumber \] y por lo tanto\[2^{32}+1\equiv 0\pmod{641}.\nonumber \] Así\(641\mid (2^{32}+1)\), como se afirma. Claramente\(2^{32}+1\ne 641\), así\(2^{32}+1\) es compuesto. Por supuesto, si ya hiciste el Ejercicio 1.12.1 ya sabrás eso\[2^{32}+1=4,294,967,297=(641)\cdot(6,700,417)\nonumber \] y eso\(641\) y de hecho\(6,700,417\) son primos. Ten en cuenta que\(641\) es el\(116^{\rm th}\) prime, así que si usaste la división trial habrías tenido que dividir por 115 primos antes de llegar a uno que divida\(2^{32}+1\), y esto supone que tienes una lista de los primeros 116 primos.
Si\(m>0\) y\[a\equiv r\pmod m\text{ where }0\le r<m,\nonumber \] entonces\(a\bmod m=r\).
Ejercicios
Demostrar que para todos\(m>0\) y para todos\(a\),\[a\equiv a\bmod m\pmod m.\nonumber \]
Usando Definición\(\PageIndex{1}\), demuestre que las siguientes congruencias son ciertas:\[\begin{aligned} 385 &\equiv 322\pmod 3; \\ -385 &\equiv -322\pmod 3; \\ 1 &\equiv -17\pmod 3; \\ 33 &\equiv 0\pmod 3. \end{aligned}\]
Utilice el Teorema\(\PageIndex{1}\) para demostrar que las congruencias en Ejercicio\(\PageIndex{2}\) son válidas.
- Mostrar que\(a\) es par si y solo si\(a\equiv 0\pmod 2\), y\(a\) es extraño si y solo si\(a\equiv 1\pmod 2\).
- Mostrar que\(a\) es par si y solo si\(a \bmod 2 = 0\), y\(a\) es extraño si y solo si\(a \bmod 2 = 1\).
(Nota: tus respuestas a las partes (a) y (b) serán similares, ¡pero no deberían ser idénticas! Haga todo lo posible para usar el vocabulario correctamente.)
Mostrar que si\(m>0\) y\(a\) es cualquier entero, hay un entero único\(r\in\{0,1,2,\dotsc,m-1\}\) tal que\(a\equiv r\pmod m\).
Encontrar enteros\(a\) y\(b\) tal que\(0<a<15\),\(0<b<15\) y\(ab\equiv 0\pmod{15}\).
Encuentra tres pares separados\(a,b\) de números enteros tales que\(1<a<15\),\(1<b<15\), y\(ab\equiv 1\pmod{15}\).
Demostrar que si\(d\mid m\) y\(d>0\), entonces\[a\equiv b\pmod m\Rightarrow a\equiv b\pmod d.\nonumber \]
Encuentra el valor de cada uno de los siguientes (¡sin usar computadora!).
- \(2^{32}\bmod 7\)
- \(10^{35}\bmod 7\)
- \(3^{35}\bmod 7\)
(Pista: Use el teorema\(\PageIndex{4}\) y las ideas utilizadas en el Ejemplo\(\PageIndex{3}\).)
Vamos\(\gcd\left(m_1,m_2\right)=1\). Demostrar que\[a\equiv b\pmod{m_1} \quad \text{ and } \quad a\equiv b\pmod{m_2}\nonumber \] si y solo si\[a\equiv b\pmod{m_1m_2}.\nonumber \]
(Pista: use Lemma 1.12.1.)