5.2: Introducción a la Teoría de Números

Template:MathjaxLevin

Hemos utilizado los números naturales para resolver problemas. Este era el conjunto correcto de números para trabajar en matemáticas discretas porque siempre nos ocupamos de un número entero de cosas. Los números naturales han sido una herramienta. Tomemos un momento para inspeccionar esa herramienta. ¿Qué descubrimientos matemáticos podemos hacer sobre los propios números naturales?

Esta es la cuestión principal de la teoría de números: una enorme, antigua, compleja, y sobre todo, hermosa rama de las matemáticas. Históricamente, la teoría de números era conocida como la Reina de las Matemáticas y era en gran medida una rama de las matemáticas puras, estudiada por su propio bien en lugar de como un medio para comprender las aplicaciones del mundo real. Sin embargo, esto ha cambiado en los últimos años, ya que se han desenterrado aplicaciones de la teoría de números. Probablemente el ejemplo más conocido de esto es la criptografía RSA, uno de los métodos utilizados para cifrar datos en internet. Es la teoría de números la que lo hace posible.

¿Qué tipo de preguntas pertenecen al ámbito de la teoría de números? Aquí hay un ejemplo motivador. Recordemos en nuestro estudio de inducción, preguntamos:

¿Qué cantidades de franqueo se pueden hacer exactamente usando solo sellos de 5 y 8 centavos?

Pudimos demostrar que se podría hacer cualquier cantidad mayor a 27 centavos. Quizás te preguntes qué pasaría si cambiáramos la denominación de los sellos. ¿Y si en cambio tuviéramos sellos de 4 y 9 centavos? ¿Habría alguna cantidad después de la cual todos los montos serían posibles? Bueno, de nuevo, podríamos reemplazar dos sellos de 4 centavos por uno de 9 centavos, o tres sellos de 9 centavos por siete sellos de 4 centavos. En cada caso podemos crear un centavo más de franqueo. Usar esto como caso inductivo nos permitiría probar que se puede hacer cualquier cantidad de franqueo mayor a 23 centavos.

Y si tuviéramos sellos de 2 centavos y 4 centavos. Aquí se ve menos prometedor. Si tomamos algún número de sellos de 2 centavos y algún número de sellos de 4 centavos, ¿qué podemos decir del total? ¿Alguna vez podría ser extraño? No lo parece.

¿Por qué funcionan 5 y 8, 4 y 9, pero 2 y 4 no funcionan? ¿Qué tienen estos números? Si te diera un par de números, ¿podrías decirme enseguida si funcionarían o no? Vamos a responder a estas preguntas, y más, después de investigar primero algunas propiedades más simples de los propios números.

Divisibilidad

Es fácil sumar y multiplicar números naturales. Si extendemos nuestro enfoque a todos los enteros, entonces la resta también es fácil (necesitamos los números negativos para poder restar cualquier número de cualquier otro número, incluso mayor de menor). División es la primera operación que presenta un reto. Si quisiéramos extender nuestro conjunto de números para que cualquier división fuera posible (tal vez excluyendo la división por 0) tendríamos que mirar los números racionales (el conjunto de todos los números que se pueden escribir como fracciones). Esto estaría yendo demasiado lejos, por lo que rechazaremos esta opción.

De hecho, es bueno que no todos los números puedan dividirse por otros números. Esto nos ayuda a comprender la estructura de los números naturales y abre la puerta a muchas preguntas y aplicaciones interesantes.

Si se dan números\(a\) y\(b\text{,}\) es posible que\(a \div b\) da un número entero. En este caso, decimos que\(b\) divide\(a\text{,}\) en símbolos, escribimos\(b \mid a\text{.}\) Si esto se mantiene, entonces\(b\) es un divisor o factor de\(a\text{,}\) y\(a\) es un múltiplo de\(b\text{.}\) En otras palabras, si\(b \mid a\text{,}\) entonces\(a = bk\) para algún entero\(k\) (esto es diciendo\(a\) es algún múltiplo de\(b\)).

La relación de divisibilidad

Dados enteros\(m\) y\(n\text{,}\) decimos “\(m\)divide\(n\)” y escribimos

\ comenzar {ecuación*} m\ mediados n\ final {ecuación*}

siempre\(n \div m\) es un número entero. Así, las siguientes aseveraciones significan lo mismo:

1. \(m \mid n\)
2. \(n = mk\)para algún número entero\(k\)
3. \(m\)es un factor (o divisor) de\(n\)
4. \(n\)es un múltiplo de\(m\text{.}\)

Observe que\(m \mid n\) es una declaración. Es cierto o falso. Por otro lado,\(n \div m\) o\(n/m\) es algún número. Si queremos afirmar que no\(n/m\) es un entero, entonces\(m\) no divide\(n\text{,}\) entonces podemos escribir\(m \nmid n\text{.}\)

Ejemplo\(\PageIndex{1}\)

Decidir si cada una de las siguientes afirmaciones son verdaderas o falsas.

1. \(4 \mid 20\)
2. \(20 \mid 4\)
3. \(0 \mid 5\)
4. \(5 \mid 0\)
5. \(7 \mid 7\)
6. \(1 \mid 37\)
7. \(-3 \mid 12\)
8. \(8 \mid 12\)
9. \(1642 \mid 136299\)

Solución

1. Cierto. 4 “entra” 20 cinco veces sin resto. En otras palabras,\(20 \div 4 = 5\text{,}\) an integer. We could also justify this by saying that \(20\) is a multiple of 4: \(20 = 4\cdot 5\text{.}\)
2. Falso. Si bien 20 es un múltiplo de 4, es falso que\(4\) is a multiple of 20.
3. Falso. \(5 \div 0\) is not even defined, let alone an integer.
4. Cierto. De hecho,\(x \mid 0\) is true for all \(x\text{.}\) This is because 0 is a multiple of every number: \(0 = x\cdot 0\text{.}\)
5. Cierto. De hecho,\(x \mid x\) is true for all \(x\text{.}\)
6. Cierto. 1 divide cada número (que no sea 0).
7. Cierto. Los números negativos funcionan bien para la relación de divisibilidad. Aquí\(12 = -3 \cdot 4\text{.}\) It is also true that \(3 \mid -12\) and that \(-3 \mid -12\text{.}\)
8. Falso. Tanto el 8 como el 12 son divisibles por 4, pero esto no quiere decir que\(12\) is divisible by \(8\text{.}\)
9. Falso. Ver abajo.

Este último ejemplo plantea una pregunta: cómo podría uno decidir si Por\(m \mid n\text{?}\) supuesto, si tuvieras una calculadora de confianza, podrías pedirle el valor de\(n \div m\text{.}\) Si escupe algo que no sea un entero, ya sabes\(m \nmid n\text{.}\) Esto parece un poco como hacer trampa: no tenemos división, así que debería ¿realmente usamos la división para verificar la divisibilidad?

Si bien en realidad no sabemos dividir, sí sabemos cómo multiplicar. Podríamos intentar multiplicar\(m\) por números cada vez más grandes hasta que nos acerquemos a\(n\text{.}\) ¿Qué tan cerca? Bueno, queremos estar seguros de que si multiplicamos\(m\) por el siguiente entero más grande, repasamos\(n\text{.}\)

Por ejemplo, intentemos esto para decidir si\(1642 \mid 136299\text{.}\) Empezar a encontrar múltiplos de 1642:

\ begin {ecuación*} 1642\ cdot 2 = 3284\ qquad 1642\ cdot 3 = 4926\ qquad 1642\ cdot 4 = 6568\ qquad\ cdots\ end {ecuación*}

Todos estos son bien menos de 136299. Supongo que podemos adelantarnos un poco:

\ begin {ecuación*} 1642\ cdot 50 = 82100\ qquad 1642\ cdot 80 = 131360\ qquad 1642\ cdot 85 = 139570\ final {ecuación*}

Ah, entonces tenemos que buscar en algún lugar entre el 80 y el 85. Prueba 83:

\ begin {ecuación*} 1642\ cdot 83 = 136286\ fin {ecuación*}

¿Esto es lo mejor que podemos hacer? ¿Qué tan lejos estamos de nuestro deseado 136299? Si restamos, obtenemos\(136299 - 136286 = 13\text{.}\) Así que sabemos que no podemos subir al 84, eso va a ser demasiado. En otras palabras, hemos encontrado que

\ begin {ecuación*} 136299 = 83\ cdot 1642 + 13\ end {ecuación*}

Ya que ahora\(13 < 1642\text{,}\) podemos decir con seguridad que\(1642 \nmid 136299\text{.}\)

Resulta que el proceso por el que pasamos arriba se puede repetir para cualquier par de números. Siempre podemos escribir el número\(a\) como algún múltiplo del número\(b\) más algún resto. Esto lo sabemos porque sabemos de división con resto de la escuela primaria. Esta es solo una manera de decirlo usando la multiplicación. Debido a la naturaleza procesal que se puede utilizar para encontrar el resto, este hecho suele llamarse algoritmo de división:

El algoritmo de división

Dados dos enteros cualesquiera\(a\) y siempre\(b\text{,}\) podemos encontrar un entero\(q\) tal que

\ begin {ecuación*} a = qb + r\ end {ecuación*}

donde\(r\) es un entero que satisface\(0 \le r < |b|\)

La idea es que siempre podamos tomar un múltiplo lo suficientemente grande como\(b\) para que el resto\(r\) sea lo más pequeño posible. Sí permitimos la posibilidad de\(r = 0\text{,}\) en qué caso tenemos\(b \mid a\text{.}\)

Clases de resto

El algoritmo de división nos dice que solo hay restos\(b\) posibles al dividir por\(b\text{.}\) Si arreglamos este divisor, podemos agrupar enteros por el resto. A cada grupo se le llama módulo de clase de resto\(b\) (o a veces clase de residuo).

Ejemplo\(\PageIndex{2}\)

Describir el resto clases módulo\(5\text{.}\)

Solución

Queremos clasificar los números por lo que sería su resto cuando se dividen por\(5\text{.}\) From the division algorithm, we know there will be exactly 5 remainder classes, because there are only 5 choices for what \(r\) could be (\(0 \le r < 5\)).

Primero considere\(r = 0\text{.}\) Here we are looking for all the numbers divisible by \(5\) since \(a = 5q+0\text{.}\) In other words, the multiples of 5. We get the infinite set

\ begin {ecuación*}\ {\ ldots, -15, -10, -5, 0, 5, 10, 15, 20,\ ldots\}\ end {ecuación*}

Observe que también incluimos enteros negativos.

Siguiente considerar\(r = 1\text{.}\) Which integers, when divided by 5, have remainder 1? Well, certainly 1, does, as does 6, and 11. Negatives? Here we must be careful: \(-6\) does NOT have remainder 1. We can write \(-6 = -2\cdot 5 + 4\) or \(-6 = -1 \cdot 5 - 1\text{,}\) but only one of these is a “correct” instance of the division algorithm: \(r = 4\) since we need \(r\) to be non-negative. So in fact, to get \(r = 1\text{,}\) we would have \(-4\text{,}\) or \(-9\text{,}\) etc. Thus we get the remainder class

\ begin {ecuación*}\ {\ lpuntos, -14, -9, -4, 1, 6, 11, 16, 21,\ lpuntos\}\ end {ecuación*}

Quedan tres más por recorrer. Las clases restantes para\(2\text{,}\) \(3\text{,}\) and \(4\) are, respectively

\ begin {ecuación*}\ {\ ldots, -13, -8, -3, 2, 7, 12, 17, 22,\ ldots\}\ end {ecuación*}\ begin {ecuación*}\ {\ ldots, -12, -7, -2, 3, 8, 13, 18, 23,\ ldots\}\ end {ecuación*}\ begin {ecuación*}\ {\ lpuntos, -11, -6, -1, 4, 9, 14, 19, 24,\ ldots\}. \ end {ecuación*}

Tenga en cuenta que en el ejemplo anterior, cada entero está exactamente en una clase restante. La forma técnica de decir esto es que el resto clases módulo\(b\) forman una partición de los enteros. ¹ Es posible desarrollar una teoría matemática de particiones, probar declaraciones sobre todas las particiones en general y luego aplicar esas observaciones a nuestro caso aquí. El hecho más importante de las particiones, es que es posible definir una relación de equivalencia a partir de una partición: se trata de una relación entre pares de números que actúa de todas las formas importantes como la relación de “iguales”. ² De nuevo, existe una teoría matemática de las relaciones de equivalencia que se aplica en muchas más instancias que la que vemos aquí.

Todo el lenguaje técnico divertido a un lado, la idea es realmente simple. Si dos números pertenecen a la misma clase de resto, entonces de alguna manera, son iguales. Es decir, son los mismos hasta la división por\(b\). En el caso donde\(b = 5\) arriba, los números\(8\) y\(23\text{,}\) aunque no sea el mismo número, son los mismos a la hora de dividir por 5, porque ambos tienen resto\(3\text{.}\)

Importa lo que es el divisor:\(8\) y\(23\) son los mismos hasta la división por\(5\text{,}\) pero no hasta la división por\(7\text{,}\) ya que\(8\) tiene resto de 1 cuando se divide por 7 mientras que 23 tiene un resto de 2.

Con todo esto en mente, introduzcamos alguna notación. Queremos decir eso\(8\) y 23 son básicamente lo mismo, aunque no sean iguales. Sería un error decir\(8 = 23\text{.}\) En cambio, escribimos\(8 \equiv 23\text{.}\) Pero esto no siempre es cierto. Funciona si estamos pensando en dividir por 5, así que tenemos que denotar eso de alguna manera. Lo que realmente vamos a escribir es esto:

\ begin {ecuación*} 8\ equiv 23\ pmod {5}\ end {ecuación*}

que se lee, “8 es congruente con 23 módulo 5” (o simplemente “mod 5”). Por supuesto entonces podríamos observar que

\ begin {ecuación*} 8\ not\ equiv 23\ pmod {7}\ end {ecuación*}

Congruencia Modulo\(n\)

Decimos que \(a\)es congruente con\(b\) módulo\(n\), y escribimos,

\ comenzar {ecuación*} a\ equiv b\ pmod {n}\ fin {ecuación*}

proporcionado\(a\) y\(b\) tener el mismo resto cuando se divide por\(n\text{.}\) En otras palabras, siempre\(a\) y\(b\) pertenecen a la misma clase de resto módulo\(n\text{.}\)

Muchos libros definen el módulo de congruencia de manera\(n\) ligeramente diferente. Dicen que\(a \equiv b \pmod{n}\) si y solo si\(n \mid a-b\text{.}\) En otras palabras, dos números son congruentes modulo\(n\text{,}\) si su diferencia es un múltiplo de\(n\text{.}\) Entonces, ¿qué definición es correcta? Resulta, no importa: son equivalentes.

Para ver por qué, considera dos números\(a\) y\(b\) cuáles son congruentes módulo\(n\text{.}\) Entonces\(a\) y\(b\) tienen el mismo resto cuando se dividen por\(n\text{.}\) Tenemos

\ begin {ecuación*} a = q_1 n + r\ qquad\ qquad b = q_2 n + r\ end {ecuación*}

Aquí los dos\(r\) son realmente iguales. Considera lo que obtenemos cuando tomamos la diferencia de\(a\) y\(b\text{:}\)

\ start {ecuación*} a-b = q_1n + r - (q_2n + r) = q_1n - q_2 n = (q_1-q_2) n\ end {ecuación*}

Así\(a-b\) es un múltiplo de\(n\text{,}\) o equivalentemente,\(n \mid a-b\text{.}\)

Por otro lado, si asumimos primero que\(n \mid a-b\text{,}\) así\(a-b = kn\text{,}\) entonces consideramos qué sucede si\(n\text{.}\) dividimos cada término por Dividir\(a\) por\(n\) dejará algún resto, como lo hará dividir\(b\) por\(n\text{.}\) Sin embargo, dividir\(kn\) por\(n\) dejará 0 resto. Por lo que los restos del lado izquierdo deben cancelar. Es decir, los restos deben ser los mismos.

Así tenemos:

Congruencia y divisibilidad

Para cualquier número entero\(a\text{,}\)\(b\text{,}\) y\(n\text{,}\) tenemos

\ begin {ecuación*} a\ equiv b\ pmod {n}\ qquad\ mbox {si y solo si}\ qquad n\ mid a-b. \ end {ecuación*}

También será útil cambiar de un lado a otro entre congruencias y ecuaciones regulares. El hecho anterior ayuda con esto. Sabemos que\(a \equiv b \pmod{n}\) si y solo si y solo\(n \mid a-b\text{,}\) si\(a-b = kn\) por algún entero\(k\text{.}\) Reordenando esa ecuación, obtenemos\(a = b + kn\text{.}\) En otras palabras, si\(a\) y\(b\) son congruentes modulo\(n\text{,}\) entonces\(a\) es\(b\) más que algún múltiplo de\(n\text{.}\) Este se ajusta a nuestra observación anterior de que todos los números en una clase de resto particular son la misma cantidad mayor que los múltiplos de\(n\text{.}\)

Congruencia e Igualdad

Para cualquier número entero\(a\text{,}\)\(b\text{,}\) y\(n\text{,}\) tenemos

\ begin {ecuación*} a\ equiv b\ pmod {n}\ qquad\ mbox {si y solo si}\ qquad a = b + kn\ mbox {para algún entero} k. \ end {ecuación*}

Propiedades de Congruencia

Dijimos antes que el módulo de congruencia\(n\) se comporta, de muchas maneras importantes, de la misma manera que lo hace la igualdad. Específicamente, podríamos probar que el módulo de congruencia\(n\) es una relación de equivalencia, lo que requeriría verificar los siguientes tres hechos:

Congruencia Modulo\(n\) is an Equivalence Relation

Dado cualquier número entero\(a\text{,}\)\(b\text{,}\) y\(c\text{,}\) y cualquier entero positivo,\(n\text{,}\) la siguiente retención:

1. \(a \equiv a \pmod{n}\text{.}\)
2. Si\(a \equiv b \pmod{n}\) entonces\(b \equiv a \pmod{n}\text{.}\)
3. Si\(a \equiv b \pmod{n}\) y\(b \equiv c \pmod{n}\text{,}\) entonces\(a \equiv c \pmod{n}\text{.}\)

En otras palabras, el módulo de congruencia\(n\) es reflexivo, simétrico y transitivo, así es una relación de equivalencia.

Deberías tomarte un minuto para convencerte de que cada una de las propiedades anteriores realmente tienen congruencia. Intente explicar cada uno usando tanto el resto como las definiciones de divisibilidad.

A continuación, considere cómo se comporta la congruencia al hacer aritmética básica. Ya sabemos que si restas dos números congruentes, el resultado será congruente a 0 (ser un múltiplo de\(n\)). ¿Y si agregamos algo congruente a 1 a algo congruente con 2? ¿Obtendremos algo congruente a 3?

Congruencia y Aritmética

Supongamos\(a \equiv b \pmod{n}\) y\(c \equiv d \pmod{n}\text{.}\) Luego se mantienen los siguientes:

1. \(a+c \equiv b+d \pmod{n}\text{.}\)
2. \(a-c \equiv b-d \pmod{n}\text{.}\)
3. \(ac \equiv bd \pmod{n}\text{.}\)

Los hechos anteriores podrían escribirse un poco extrañamente, pero la idea es simple. Si tenemos una verdadera congruencia, y agregamos lo mismo a ambos lados, el resultado sigue siendo una verdadera congruencia. Esto suena como que estamos diciendo:

Si\(a \equiv b \pmod{n}\) entonces\(a+c \equiv b+c \pmod{n}\text{.}\)

Por supuesto que esto también es cierto, es el caso especial donde\(c = d\text{.}\) Pero lo que tenemos funciona en más generalidad. Piense en la congruencia como “básicamente igual”. Si tenemos dos números que son básicamente iguales, y agregamos básicamente lo mismo a ambos lados, el resultado será básicamente igual.

Esto parece razonable. ¿Es realmente cierto? Demostremos el primer hecho:

Prueba

Supongamos\(a \equiv b \pmod{n}\) y\(c \equiv d \pmod{n}\text{.}\) Eso significa\(a = b + kn\) y\(c = d + jn\) para enteros\(k\) y\(j\text{.}\) Sumar estas ecuaciones:

\ comenzar {ecuación*} a+c = b+d + kn + jn. \ end {ecuación*}

Pero\(kn + jn = (k+j)n\text{,}\) que es solo un múltiplo de\(n\text{.}\)\(a+c = b+d + (j+k)n\text{,}\) So o en otras palabras,\(a+c \equiv b+d \pmod{n}\)

\(\square\)

Los otros dos hechos pueden probarse de manera similar.

Una de las consecuencias importantes de estos hechos sobre congruencias, es que básicamente podemos reemplazar cualquier número en una congruencia con cualquier otro número con el que sea congruente. Aquí hay algunos ejemplos para ver cómo (y por qué) eso funciona:

Ejemplo\(\PageIndex{3}\)

Encuentra el resto de\(3491\) dividido por\(9\text{.}\)

Solución

Podríamos hacer división larga, pero hay otra manera. Queremos encontrar\(x\) such that \(x \equiv 3491 \pmod{9}\text{.}\) Now \(3491 = 3000 + 400 + 90 + 1\text{.}\) Of course \(90 \equiv 0 \pmod 9\text{,}\) so we can replace the 90 in the sum with 0. Why is this okay? We are actually subtracting the “same” thing from both sides:

\ begin {ecuation*}\ begin {alineado} x\ amp\ equiv 3000 + 400 + 90 + 1\ pmod 9\\ - ~~ 0\ amp\ equiv 90\ pmod 9\\ x\ amp\ equiv 3000 + 400 + 0 + 1\ pmod 9. \ end {alineado}\ end {ecuación*}

A continuación, tenga en cuenta que\(400 = 4 \cdot 100\text{,}\) and \(100 \equiv 1 \pmod 9\) (since \(9 \mid 99\)). So we can in fact replace the 400 with simply a 4. Again, we are appealing to our claim that we can replace congruent elements, but we are really appealing to property 3 about the arithmetic of congruence: we know \(100 \equiv 1 \pmod{9}\text{,}\) so if we multiply both sides by \(4\text{,}\) we get \(400 \equiv 4 \pmod 9\text{.}\)

De igual manera, podemos sustituir 3000 por 3, ya que\(1000 = 1 + 999 \equiv 1 \pmod 9\text{.}\) So our original congruence becomes

\ comenzar {ecuación*} x\ equiv 3 + 4 + 0 + 1\ pmod 9\ final {ecuación*}\ comenzar {ecuación*} x\ equiv 8\ pmod 9. \ end {ecuación*}

Por lo tanto\(3491\) divided by 9 has remainder 8.

El ejemplo anterior debería convencerte de que la conocida prueba de divisibilidad para 9 es verdadera: la suma de los dígitos de un número es divisible por 9 si y solo si el número original es divisible por 9. De hecho, ahora sabemos algo más: cualquier número es congruente con la suma de sus dígitos, módulo 9. ³ Esto también funciona para 3, pero definitivamente no para ningún módulo en general.

Intentemos otro:

Ejemplo\(\PageIndex{4}\)

Encuentra el resto cuando\(3^{123}\) se divide por 7.

Solución

Por supuesto, estamos trabajando con congruencia porque queremos encontrar los más pequeños positivos\(x\) such that \(x \equiv 3^{123} \pmod 7\text{.}\) Now first write \(3^{123} = (3^3)^{41}\text{.}\) We have:

\ begin {ecuación*} 3^ {123} = 27^ {41}\ equiv 6^ {41}\ pmod 7,\ end {ecuación*}

desde\(27 \equiv 6 \pmod 7\text{.}\) Notice further that \(6^2 = 36\) is congruent to 1 modulo 7. Thus we can simplify further:

\ begin {ecuación*} 6^ {41} = 6\ cdot (6^2) ^ {20}\ equiv 6\ cdot 1^ {20}\ pmod 7. \ end {ecuación*}

Pero\(1^{20} = 1\text{,}\) so we are done:

\ begin {ecuación*} 3^ {123}\ equiv 6\ pmod 7. \ end {ecuación*}

En el ejemplo anterior, estamos usando el hecho de que si\(a \equiv b \pmod n\text{,}\) entonces\(a^p \equiv b^p \pmod n\text{.}\) Esto es solo aplicar propiedad 3 un montón de veces.

Hasta el momento hemos visto cómo sumar, restar y multiplicar con congruencias. ¿Qué pasa con la división? Hay una razón por la que hemos esperado para discutirlo. Resulta que no podemos simplemente dividir. Es decir, aunque no lo\(ad \equiv bd \pmod n\text{,}\) sepamos\(a \equiv b \pmod n\text{.}\) Consideremos, por ejemplo:

\ begin {ecuación*} 18\ equiv 42\ pmod 8. \ end {ecuación*}

Esto es cierto. Ahora\(18\) y ambos\(42\) son divisibles por 6. Sin embargo,

\ begin {ecuación*} 3\ not\ equiv 7\ pmod 8. \ end {ecuación*}

Si bien esto no funciona, tenga en cuenta que No\(3 \equiv 7 \pmod 4\text{.}\) podemos dividir\(8\) por 6, pero podemos dividir 8 por el mayor factor común de\(8\) y\(6\text{.}\) ¿Esto siempre sucederá?

Supongamos\(ad \equiv bd \pmod n\text{.}\) En otras palabras, tenemos\(ad = bd + kn\) para algún entero Por\(k\text{.}\) supuesto que\(ad\) es divisible por\(d\text{,}\) como es\(bd\text{.}\) Así también\(kn\) debe ser divisible por\(d\text{.}\) Ahora si\(n\) y no\(d\) tenemos factores comunes (distintos a 1), entonces debemos tener\(d \mid k\text{.}\) Pero en general, si tratamos de dividir\(kn\) por no\(d\text{,}\) sabemos que obtendremos un múltiplo entero de\(n\text{.}\) Algunos de los\(n\) podrían dividirse también. Para estar seguros, dividamos todo\(n\) lo que podamos. Toma el factor más grande de ambos\(d\)\(n\text{,}\) y y cancela eso de\(n\text{.}\) El resto de los factores de\(d\) vendrá de\(k\text{,}\) ningún problema.

Llamaremos al factor más grande de ambos\(d\) y\(n\) al\(\gcd(d,n)\text{,}\) mayor divisor común. En nuestro ejemplo anterior,\(\gcd(6,8) = 2\) ya que el mayor divisor común a 6 y 8 es 2.

Congruencia y División

Supongamos\(ad \equiv bd \pmod n\text{.}\) Entonces\(a \equiv b \pmod{\frac{n}{\gcd(d,n)}}\text{.}\)

Si\(d\) y no\(n\) tienen factores en común entonces\(\gcd(d,n) = 1\text{,}\) entonces\(a \equiv b \pmod n\text{.}\)

Ejemplo\(\PageIndex{5}\)

Simplificar las siguientes congruencias mediante división: (a)\(24 \equiv 39 \pmod 5\) y (b)\(24 \equiv 39 \pmod{15}\text{.}\)

Solución

a) Ambos\(24\) and \(39\) are divisible by \(3\text{,}\) and \(3\) and \(5\) have no common factors, so we get

\ begin {ecuación*} 8\ equiv 13\ pmod 5. \ end {ecuación*}

(b) Nuevamente, podemos dividir por 3. Sin embargo, hacerlo ciegamente nos da\(8 \equiv 13 \pmod{15}\) which is no longer true. Instead, we must also divide the modulus 15 by the greatest common factor of \(3\) and \(15\text{,}\) which is \(3\text{.}\) Again we get

\ begin {ecuación*} 8\ equiv 13\ pmod 5. \ end {ecuación*}

Resolviendo Congruencias

Ahora que tenemos algunas reglas algebraicas para gobernar las relaciones de congruencia, podemos intentar resolver por un desconocido en una congruencia. Por ejemplo, ¿hay un valor de\(x\) que satisfaga,

\ begin {ecuación*} 3x + 2\ equiv 4\ pmod {5},\ end {ecuación*}

y si es así, ¿qué es?

En este ejemplo, ya que el módulo es pequeño, simplemente podríamos probar cada valor posible para Realmente solo\(x\text{.}\) hay 5 a considerar, ya que cualquier entero que satisfizo la congruencia podría ser reemplazado por cualquier otro entero que fuera congruente con el módulo 5. Aquí, cuando\(x = 4\) obtenemos\(3x + 2 = 14\) lo cual es efectivamente congruente con 4 módulo 5. Esto significa que\(x = 9\) y\(x = 14\)\(x = 19\) y así sucesivamente cada uno también será una solución porque como vimos anteriormente, reemplazar cualquier número en una congruencia por un número congruente no cambia la verdad de la congruencia.

Entonces en este ejemplo, simplemente computar\(3x + 2\) para valores de\(x \in \{0,1,2,3,4\}\text{.}\) Esto da 2, 5, 8, 11, y 14 respectivamente, para lo cual sólo 14 es congruente con 4.

Veamos también cómo podrías resolver esto usando nuestras reglas para el álgebra de congruencias. Tal enfoque sería mucho más sencillo que la táctica de ensayo y error si el módulo fuera mayor. Primero, sabemos que podemos restar 2 de ambos lados:

\ begin {ecuación*} 3x\ equiv 2\ pmod {5}. \ end {ecuación*}

Después para dividir ambos lados por 3, primero agregamos 0 a ambos lados. Por supuesto, en el lado derecho, queremos que ese 0 sea un 10 (sí,\(10\) realmente es 0 ya que son congruentes módulo 5). Esto da,

\ begin {ecuación*} 3x\ equiv 12\ pmod {5}. \ end {ecuación*}

Ahora divide ambos lados por 3. Ya\(\gcd(3,5) = 1\text{,}\) que no necesitamos cambiar el módulo:

\ begin {ecuación*} x\ equiv 4\ pmod {5}. \ end {ecuación*}

Observe que esto de hecho da la solución general: no sólo puede\(x = 4\text{,}\) sino que\(x\) puede ser cualquier número que sea congruente a 4. Podemos dejarlo así, o escribir “\(x = 4 + 5k\)para cualquier entero\(k\text{.}\)”

Ejemplo\(\PageIndex{6}\)

Resuelve las siguientes congruencias para\(x\text{.}\)

1. \(7x \equiv 12 \pmod{13}\text{.}\)
2. \(84x - 38 \equiv 79 \pmod{15}\text{.}\)
3. \(20x \equiv 23 \pmod{14}\text{.}\)

Solución

1. Todo lo que tenemos que hacer aquí es dividir ambos lados por 7. Agregamos 13 al lado derecho repetidamente hasta que obtenemos un múltiplo de 7 (agregar 13 es lo mismo que agregar 0, entonces esto es legal). Obtenemos\(25\text{,}\) \(38\text{,}\) \(51\text{,}\) \(64\text{,}\) \(77\) – got it. So we have:\ begin {equation*}\ begin {aligned} 7x\ amp\ equiv 12\ pmod {13}\\ 7x\ amp\ equiv 77\ pmod {13}\\ x\ amp\ equiv 11\ pmod {13}. \ end {alineado}\ end {ecuación*}
2. Aquí, dado que tenemos números mayores que el módulo, podemos reducirlos antes de aplicar cualquier álgebra. Tenemos\(84 \equiv 9\text{,}\) \(38 \equiv 8\) and \(79 \equiv 4\text{.}\) Thus,\ comenzar {ecuación*}\ comenzar {alineado} 84x - 38\ amp\ equiv 79\ pmod {15}\\ 9x - 8\ amp\ equiv 4\ pmod {15}\\ 9x\ amp\ equiv 12\ pmod {15}\\ 9x\ amp\ equiv 72\ pmod {15}. \ end {aligned}\ end {equation*} Obtuvimos el 72 sumando\(0 \equiv 60 \pmod{15}\) to both sides of the congruence. Now divide both sides by 9. However, since \(\gcd(9, 15) = 3\text{,}\) we must divide the modulus by 3 as well:\ begin {equation*} x\ equiv 8\ pmod 5. \ end {equation*} Así que las soluciones son aquellos valores que son congruentes con 8, o equivalentemente 3, módulo 5. Esto quiere decir que en cierto sentido existen 3 soluciones módulo 15:3, 8 y 13. Podemos escribir la solución:\ begin {equation*} x\ equiv 3\ pmod {15}; ~~ x\ equiv 8\ pmod {15}; ~~x\ equiv 13\ pmod {15}. \ end {ecuación*}
3. Primero, reducir el módulo 14:\ begin {equation*} 20x\ equiv 23\ pmod {14}\ end {equation*}\ begin {equation*} 6x\ equiv 9\ pmod {14}. \ end {equation*} Ahora podríamos dividir ambos lados por 3, o intentar aumentar 9 por un múltiplo de 14 para obtener un múltiplo de 6. Si dividimos por 3, obtenemos,\ begin {ecuación*} 2x\ equiv 3\ pmod {14}. \ end {equation*} Ahora intenta sumar múltiplos de 14 a 3, con la esperanza de conseguir un número podemos dividir por 2. ¡Esto no va a funcionar! Cada vez que sumamos 14 al lado derecho, el resultado seguirá siendo impar. Nunca conseguiremos un número par, así que nunca podremos dividirnos por 2. Por lo tanto, no hay soluciones a la congruencia.

La última congruencia anterior ilustra la manera en que las congruencias podrían no tener soluciones. De hecho, podríamos haber visto esto de inmediato. Mira la congruencia original:

\ begin {ecuación*} 20x\ equiv 23\ pmod {14}. \ end {ecuación*}

Si escribimos esto como una ecuación, obtenemos

\ begin {ecuación*} 20x = 23 + 14k,\ end {ecuación*}

o equivalentemente\(20x - 14k = 23\text{.}\) Podemos ver fácilmente que no habrá solución a esta ecuación en enteros. El lado izquierdo siempre será par, pero el lado derecho es impar. Un problema similar ocurriría si el lado derecho fuera divisible por cualquier número el lado izquierdo no lo fuera.

Entonces, en general, dada la congruencia

\ comenzar {ecuación*} hacha\ equiv b\ pmod {n},\ fin {ecuación*}

si\(a\) y\(n\) son divisibles por un número que no\(b\) es divisible por, entonces no habrá soluciones. De hecho, en realidad solo necesitamos verificar un divisor de\(a\) y\(n\text{:}\) el mayor divisor común. Así, una forma más compacta de decir esto es:

Congruencias sin soluciones

Si\(\gcd(a,n) \nmid b\text{,}\) entonces no\(ax \equiv b \pmod{n}\) tiene soluciones.

Resolución de ecuaciones diofantinas lineales

La matemática discreta se ocupa de números enteros de cosas. Entonces, cuando queremos resolver ecuaciones, generalmente estamos buscando soluciones de enteros. Las ecuaciones que pretenden tener solo soluciones enteras fueron estudiadas por primera vez en el siglo III por el matemático griego Diofanto de Alejandría, y como tales se denominan ecuaciones diofantinas. Probablemente el ejemplo más famoso de una ecuación diofantina es\(a^2 + b^2 = c^2\text{.}\) Las soluciones enteras a esta ecuación se llaman triples pitagóricos. En general, resolver ecuaciones diofantinas es difícil (de hecho, no existe un algoritmo general para decidir si una ecuación diofantina tiene una solución, un resultado conocido como Teorema de Matiyasevich). Restringiremos nuestro enfoque a las ecuaciones diofantinas lineales, que son considerablemente más fáciles de trabajar.

Ecuaciones diofantinas

Una ecuación en dos o más variables se denomina ecuación diofantina si solo las soluciones de números enteros son de interés. Una ecuación diofantina lineal toma la forma\(a_1x_1 + a_2x_x + \cdots + a_nx_n = b\) para constantes\(a_1,\ldots, a_n, b\text{.}\)

Una solución a una ecuación de Diofantina es una solución a la ecuación que consiste solo en números enteros.

Tenemos las herramientas que necesitamos para resolver ecuaciones diofantinas lineales. Consideraremos, como ejemplo principal, la ecuación

\ begin {ecuación*} 51x + 87y = 123. \ end {ecuación*}

La estrategia general será convertir la ecuación en una congruencia, luego resolver esa congruencia. ⁴ Ciertamente esta no es la única manera de proceder. Una técnica más común sería aplicar el algoritmo euclidiano. Nuestro camino puede ser un poco más rápido, y se presenta aquí principalmente para variedad. Trabajemos este ejemplo en particular para ver cómo podría ir esto.

Primero, comprobar si quizás no hay soluciones porque un divisor de\(51\) y no\(87\) es un divisor de\(123\text{.}\) Really, solo necesitamos verificar si\(\gcd(51, 87) \mid 123\text{.}\) Este divisor más común es 3, y si\(3 \mid 123\text{.}\) En este punto, bien podríamos factorial este mayor divisor común. Entonces, en cambio, resolveremos:

\ begin {ecuación*} 17x + 29y = 41. \ end {ecuación*}

Ahora observa que si van a haber soluciones, entonces para esos valores de\(x\) y\(y\text{,}\) los dos lados de la ecuación deben tener el mismo resto entre sí, no importa por qué dividamos. En particular, si dividimos ambos lados por 17, debemos obtener el mismo resto. Así podemos escribir con seguridad

\ begin {ecuación*} 17x + 29y\ equiv 41\ pmod {17}. \ end {ecuación*}

Elegimos 17 porque\(17x\) tendrá resto 0. Esto nos permitirá reducir la congruencia a una sola variable. También podríamos haber pasado a un módulo de congruencia 29, aunque suele haber una buena razón para seleccionar la opción más pequeña, ya que esto nos permitirá reducir el otro coeficiente. En nuestro caso, reducimos la congruencia de la siguiente manera:

\ begin {ecuación*}\ comenzar {alineado} 17x + 29y\ amp\ equiv 41\ pmod {17}\\ 0x + 12y\ amp\ equiv 7\ pmod {17}\\ 12 y\ amp\ equiv 24\ pmod {17}\\ y\ amp\ equiv 2\ pmod {17}. \ end {alineado}\ end {ecuación*}

Ahora en este punto sabemos que\(y = 2 + 17k\) funcionará para cualquier entero\(k\text{.}\) Si no hemos cometido un error, deberíamos poder volver a enchufar esto a nuestra ecuación original de Diofantinas para encontrar\(x\text{:}\)

\ comenzar {ecuación*}\ comenzar {alineado} 17x + 29 (2 + 17k)\ amp = 41\\ 17x\ amp = -17 - 29\ cdot 17k\\ x\ amp = -1-29k. \ end {alineado}\ end {ecuación*}

Ahora hemos encontrado todas las soluciones a la ecuación Diofantina. Para cada uno\(k\text{,}\)\(x = -1-29k\) y\(y = 2 + 17k\) satisfará la ecuación. Podríamos verificar esto por algunos casos. Si\(k = 0\text{,}\) la solución es\((-1,2)\text{,}\) y sí,\(-17 + 2\cdot 29 = 41\text{.}\) Si\(k = 3\text{,}\) la solución es\((-88, 53)\text{.}\) Si\(k = -2\text{,}\) conseguimos\((57, -32)\text{.}\)

Para resumir este proceso, para resolver\(ax + by = c\text{,}\) nosotros,

1. Divide ambos lados de la ecuación por\(\gcd(a,b)\) (si esto no deja el lado derecho como un entero, no hay soluciones). Supongamos que\(ax + by = c\) ya se ha reducido de esta manera.
2. Escoge el más pequeño de\(a\) y\(b\) (aquí, supongamos que es\(b\)), y convierte a un módulo de congruencia\(b\text{:}\)\ begin {equation*} ax + por\ equiv c\ pmod {b}. \ end {equation*} Esto reducirá a una congruencia con una variable,\(x\text{:}\)\ begin {equation*} ax\ equiv c\ pmod {b}. \ end {ecuación*}
3. Resolver la congruencia como hicimos en el apartado anterior. Escribe tu solución como una ecuación, como,\ begin {equation*} x = n + kb\ end {equation*}
4. Conecte esto a la ecuación original de Diofantina y resuelva\(y\text{.}\)
5. Si queremos conocer soluciones en un rango particular (por ejemplo,\(0 \le x, y \le 20\)), elija diferentes valores de\(k\) hasta que tenga todas las soluciones requeridas.

Aquí hay otro ejemplo:

Ejemplo\(\PageIndex{7}\)

¿Cómo se puede hacer $6.37 usando solo sellos de 5 centavos y 8 centavos? ¿Cuál es el número más pequeño y mayor de sellos que podrías usar?

Solución

Primero, necesitamos una ecuación Diofantina. Trabajaremos en números de centavos. Vamos\(x\) be the number of \(5\)-cent stamps, and \(y\) be the number of 8-cent stamps. We have:

\ begin {ecuación*} 5x + 8y = 637. \ end {ecuación*}

Convertir a una congruencia y resolver:

\ comenzar {ecuación*}\ comenzar {alineado} 8y\ amp\ equiv 367\ pmod {5}\\ 3y\ amp\ equiv 2\ pmod 5\\ 3y\ amp\ amp\ equiv 12\ pmod 5\\ y\ amp\ amp\ equiv 4\ pmod 5.\\ final {alineado}\ final {ecuación*}

Así\(y = 4 + 5k\text{.}\) Then \(5x + 8(4+5k) = 637\text{,}\) so \(x = 121 - 8k\text{.}\)

Esto dice que una forma de hacer $6.37 es tomar 121 de los sellos de 5 centavos y 4 de los sellos de 8 centavos. Para encontrar el menor y mayor número de sellos, pruebe diferentes valores de\(k\text{.}\)

\(k\)	\((x,y)\)	Sellos
\ (k\) "> -1	\ ((x, y)\) "> (129, -1)	no es posible
\ (k\) "> 0	\ ((x, y)\) "> (121, 4)	125
\ (k\) "> 1	\ ((x, y)\) "> (113, 9)	122
\ (k\) "> 2	\ ((x, y)\) "> (105, 13)	119
\ (k\) ">\ vdots	\ ((x, y)\) ">\ vdots	\ vdots

Esto no es ninguna sorpresa. Tener la mayor cantidad de sellos significa que tenemos tantos sellos de 5 centavos como sea posible, y para obtener el menor número de sellos requeriría tener el menor número de sellos de 5 centavos. Para minimizar el número de sellos de 5 centavos, queremos elegir\(k\) so that \(121-8k\) is as small as possible (but still positive). When \(k = 15\text{,}\) we have \(x = 1\) and \(y = 79\text{.}\)

Por lo tanto, para hacer $6.37, usted puede nosotros tan solo 80 sellos (1 sello de 5 centavos y 79 sellos de 8 centavos) o hasta 125 sellos (121 sellos de 5 centavos y 4 sellos de 8 centavos).

Usando este método, siempre y cuando puedas resolver congruencias lineales en una variable, puedes resolver ecuaciones diofantinas lineales de dos variables. Sin embargo, hay momentos en que resolver la congruencia lineal es mucho trabajo. Por ejemplo, supongamos que hay que resolver,

\ begin {ecuación*} 13x\ equiv 6\ pmod {51}. \ end {ecuación*}

Podrías seguir sumando 51 al lado derecho hasta obtener un múltiplo de 13: Obtendrías 57, 108, 159, 210, 261, 312, y 312 es el primero de estos que es divisible por 13. Esto funciona, pero en realidad es demasiado trabajo. En su lugar, podríamos volver a convertir a una ecuación Diofantina:

\ begin {ecuación*} 13x = 6 + 51k\ end {ecuación*}

Ahora resuelve esto como lo tenemos en esta sección. Escríbelo como congruencia módulo 13:

\ begin {ecuation*}\ begin {alineado} 0\ amp\ equiv 6 + 51k\ pmod {13}\\ -12k\ amp\ equiv 6\ pmod {13}\\ 2k\ amp\ amp\ equiv -1\ pmod {13}\\ 2k\ amp\ equiv 12\ pmod {13}\\ k\ amp\ equiv 6\ pmod {13}\ end {alineado}\ end {ecuación*}

así que\(k = 6 + 13j\text{.}\) ahora vuelve y averiguarlo\(x\text{:}\)

\ comenzar {ecuación*}\ comenzar {alineado} 13x\ amp = 6 + 51 (6+13j)\\ x\ amp = 24 + 51j. \ end {alineado}\ end {ecuación*}

Por supuesto que podrías hacer esto cambiando de un lado a otro entre congruencias y ecuaciones diofantinas tantas veces como quieras. Si solo usaras esta técnica, esencialmente replicarías el algoritmo euclidiano, una forma más estándar de resolver ecuaciones diofantinas.