En aritmética modular, la cuestión de cuándo una congruencia lineal puede ser resuelta se describe mediante el teorema de congruencia lineal. Si a y b dos números enteros cualesquiera y n es un número entero positivo, entonces la congruencia
(1)
tiene una solución para x si y sólo si b es divisible por el máximo común divisor d de a y n (denotado mediante mcd(a,n)). Cuando éste es el caso, y x0 es una solución de () , entonces el conjunto de todas las soluciones está dado por
En particular, existirán exactamente d = mcd(a,n) soluciones en el conjunto de residuos {0,1,2,...,n-1}.
Ejemplo[editar]
Por ejemplo, se puede examinar la ecuación ax ≡ 2 (mod 6) con diferentes valores de a para ver lo que produce:
Aquí d = mcd(3,6) = 3 pero puesto que 3 no divide a 2, entonces no hay solución.
Aquí d = mcd(5,6) = 1, el cual divide a cualquier b, y así sólo hay exactamente una única solución en {0,1,2,3,4,5}: x=4.
Aquí d = mcd(4,6) = 2, el cual divide a 2, y así sólo hay exactamente dos soluciones en {0,1,2,3,4,5}: x=2 y x=5.
Resolución de congruencias lineales[editar]
En la resolución general de ecuaciones de la forma:
si el máximo común divisor d = mcd(a, n) divide a b, entonces se puede encontrar una solución x para la congruencia como sigue: el algoritmo extendido de Euclides produce enteros r y s tales que ra + sn = d. Entonces x = rb/d es una solución. Las otras soluciones son los números congruentes con x modulo n/d.
Por ejemplo, la congruencia
tiene 4 soluciones puesto que mcd(12, 28) = 4 divide a 20. El algoritmo extendido de Euclides da (-2)*12 + 1*28 = 4, i.e. r = -2 y s = 1. Por lo tanto, una solución es x = -2*20/4 = -10, y -10 = 4 módulo 7. Todas las demás soluciones deberán ser también congruentes con 4 módulo 7. Puesto que la ecuación original usa módulo 28, El conjunto de soluciones enteras en el rango de 0 a 27 es x = {4,11,18,25}.
Sistemas de congruencias lineales[editar]
Mediante el repetido uso del teorema de la congruencia lineal, se puede también resolver sistemas de congruencias lineales, como en el siguiente ejemplo: encontrar todos los números x tales que
- 2x ≡ 2 (mod 6)
- 3x ≡ 2 (mod 7)
- 2x ≡ 4 (mod 8).
Resolviendo la primera congruencia utilizando el método expuesto arriba, se obtiene que x ≡ 1 (mod 3), el cual puede ser escrito también como x = 3k + 1. Sustituyendo éste en la segunda congruencia y simplificando, se obtiene
- 9k ≡ −1 (mod 7).
Al resolver la congruencia resulta que k ≡ 3 (mod 7), o k = 7l + 3. Se sigue entonces que x = 3 (7l + 3) + 1 = 21l + 10. Sustituyendo esto en la tercera congruencia y simplificando de nuevo, se obtiene
- 42l ≡ −16 (mod 8)
que tiene como solución l ≡ 0 (mod 4), o l = 4m. Esto produce x = 21(4m) + 10 = 84m + 10, o
- x ≡ 10 (mod 84)
que describe todas las soluciones del sistema.
En teoría de números el teorema de Euler, también conocido como teorema de Euler-Fermat, es una generalización del pequeño teorema de Fermat, y como tal afirma una proposición sobre la divisibilidad de los números enteros. El teorema establece que:
|
sin embargo, es más común encontrarlo con notación moderna en la siguiente forma:
|
donde φ(n) es la función φ de Euler.
Función φ de Euler[editar]
Si n es un número entero, la cantidad de enteros entre 1 y n que son primos relativos con n se denota como φ(n):
|
|
A la función φ se le conoce como las sigts función φ de Euler. Tal función es multiplicativa: si m y n son primos relativos, entonces
- φ(mn)=φ(m)φ(n).
Podemos verificarlo con la tabla dada arriba:
- φ(30) = φ(6)φ(5) =2·4 = 8
Congruencias[editar]
El otro concepto involucrado en el teorema de Euler es el de congruencia. En teoría de números, se dice que dos números a, b son congruentes respecto a un módulo n, cuando n divide al entero a-b. La congruencia de a, brespecto al módulo n se simboliza como a ≡ b (mod n).
La congruencia de números se comporta de manera similar a una igualdad (formalmente, es una relación de equivalencia):
- Si a≡b (mod n) entonces: a+c≡b+c (mod n) y ac ≡ bc (mod n) para cualquier entero c. Es decir, se puede sumar o multiplicar una misma cantidad a ambos lados de una congruencia y se preserva la relación.
- Si a≡b (mod n) y b≡c (mod n) entonces a≡c (mod n). Es otras palabras, la relación es transitiva.
Un ejemplo sencillo para entender la aritmética con congruencias lo proporciona un reloj de manecillas, ya que las horas en un reloj se comportan como congruencias módulo 12. Por ejemplo, las 15 y las 3 horas son indicadas por la misma posición en el reloj; esta equivalencia se escribiría como
- 15 ≡ 3 (mod 12)
y se obtiene de que 12 divide a 15-3.
Si ahora el reloj marca las 5, dentro de 30 horas marcará las 11, porque 12 divide a 35-11 =24 y así:
- 5+30 = 35 ≡ 11 (mod 12).
Una particularidad de las congruencias, que la diferencia de la igualdad común es que, aunque podemos sumar o multiplicar una misma cantidad a ambos lados de una congruencia preservándola, no podemos hacer lo mismo con una división:
- 6· 4 ≡ 3·4 (mod 6), pues 6 divide a 24-12; sin embargo no es cierto que 6 ≡ 3 (mod 6).
Sin embargo, hay un caso especial en el que sí es posible efectuar tal cancelación: cuando el factor y el módulo son primos relativos:
- Dado que 5·4 ≡ 5·10 (mod 6) y el máximo común divisor de 5 y 6 es 1 (es decir, son primos relativos), entonces podemos cancelar el 5 y obtener 4 ≡ 10 (mod 6).
Prueba del teorema de Euler[editar]
La prueba original del teorema de Euler, en notación moderna, se desarrolla en los siguientes pasos.
| Pasos generales | Ejemplo con n = 8, a = 3 |
|---|---|
| Consideremos el conjunto P de los enteros menores que n y coprimos con n | Consideremos el conjunto P = {1,3,5,7} |
| Multipliquemos cada elemento del conjunto P por a para formar el conjunto Q | Construimos el conjunto Q = {3,9,15,21} |
| Los elementos del conjunto Q son congruentes a los del elemento P (en diferente orden) (Módulo n). | 3≡3 (mod 8), 9≡1 (mod 8), 15≡7 (mod 8), 21≡5 (mod 8) |
| Sea u el producto de los elementos de P, y sea v el producto de los elementos de Q | u= 1·3·5·7 = 105, v=3·9·15·21=8505 |
| Los números v y u son congruentes pues sus factores son congruentes: v≡u (mod n) | 8505≡105 (mod 8) |
| El entero v es igual a u multiplicado por aφ(n): v=u·aφ(n) | v= 3·9·15·21 = (3·1)(3·3)(3·5)(3·7) = 34· (1·3·5·7) = 3φ(8)·105 |
| Cancelamos el factor u en la congruencia v≡u (mod n): u·aφ(n)≡u(mod n) | 3φ(8)·105 ≡105 (mod 8) |
| Concluimos aφ(n) ≡1(mod n) | 3φ(8) ≡1 (mod 8) |
Es importante recalcar que la cancelación sólo es posible puesto que u y n son primos relativos. De manera similar, el tercer paso (los elementos de Q son congruentes a los de P) sólo puede obtenerse debido a que a y nson primos relativos.
Aplicación del teorema de Euler[editar]
Una aplicación del teorema de Euler es en la resolución de ecuaciones de congruencia.
Por ejemplo, se desea encontrar todos los números x que satisfacen
-
- 5x ≡ 2 (mod 12)
en otras palabras, todos los números que al multiplicarlos por 5, dejan residuo 2 en la división por 12. O de otra forma, todos los números x tales que 12 divida a 5x-2.
El teorema de Euler dice que
-
- 5φ(12) = 54 ≡ 1 (mod 12)
por lo que, multiplicando ambos lados de la ecuación por 53:
-
- 53 · 5x ≡53·2 =250 ≡ 10 (mod 12)
- 54 x ≡ 10 (mod 12)
- x≡10 (mod 12)
Entonces, la conclusión es que, cualquier número que al dividirse por 12 tenga residuo 10, será una solución de la ecuación. Se puede verificar con un ejemplo. Si se divide 34 entre 12, el residuo es 10, por lo que x=34 debe funcionar como solución. Para verificarlo, se divide 34·5=170 entre 12, obtenemos un cociente 14 y un residuo 2, como se esperaba.
Relación con el teorema de Fermat[editar]
El teorema de Euler es una generalización del teorema de Fermat que establece:
|
Fermat estableció tal resultado en una carta a Frénicle de Bessy, pero como era usual en él, omitió la prueba del mismo:
Tout nombre premier mesure infailliblement une des puissances -1 de quelque progression que ce soit, et l’exposant de la dite puissance est sous-multiple du nombre premier donné -1. (...) Et cette proposition est généralement vraie en toutes progressions et en tous nombres premiers; de quoi je vous envoierois la démonstration, si je n'appréhendois d'être trop long. Todo número primo mide una de las potencias menos uno de cualquier progresión en la que el exponente es un múltiplo del primo dado menos uno. (...) Y esta proposición es generalmente cierta para todas las progresiones y todos los números primos; te enviaría la prueba, si no temiese que es demasiado larga.
No fue sino hasta que Euler probó su teorema, que quedó demostrado el resultado de Fermat, pues es un corolario del teorema de Euler. En notación de congruencias, el teorema de Fermat establece que
|
En la afirmación original de Fermat, no se hace explícita la suposición de que a y p son primos relativos. Dado que si p es un número primo, todos los números {1,2,3,...,p-1} son primos relativos con p, se cumple que φ(p)=p-1 y por tanto el teorema de Fermat es una consecuencia directa del teorema de Euler. Por esta razón al teorema de Euler se lo conoce en ocasiones como teorema de Euler-Fermat.
En matemáticas, particularmente en teoría de números y álgebra abstracta, el teorema de Wilson es una proposición clásica vinculada con la divisibilidad y la primalidad de números enteros. A continuación, se presenta su enunciado:
|
La proposición recíproca también es verdadera, por lo que puede afirmarse que un número n> 1 es primo si y sólo si (n− 1)! ≡ − 1 (mod n). Sin embargo, sólo la implicación de arriba es conocida como teorema de Wilson (o Congruencia de Wilson). Por tanto, el teorema, probado su recíproco, proporciona una condición necesaria y suficiente para que el número entero sea primo.1
- Enunciado alternativo
Si es un número primo entonces es divisible por .
Historia[editar]
Fue atribuido a John Wilson por Edward Waring, quien en 1770 comentó acerca de que Wilson dejara anotado el hallazgo. No hay evidencia de que Wilson hubiese hallado la demostración, y ciertamente Waring no la halló. Fue Lagrange quien, en 1771 dio la primera demostración. Con toda propiedad, el teorema debe ser atribuido a Abu 'Ali al-Hasan ibn al-Haytham, llamado en Occidente Alhazen, quien lo formuló a comienzos del siglo XI.
Ejemplo[editar]
La siguiente tabla muestra los valores de n desde 2 a 30, (n-1)!, Y el resto al (n-1)! se divide por n. (El resto cuando m se divide por n se escribe m mod n). El color de fondo es de color rosa para los valores primos de n, color verde claro para valores compuestos.
| n>1 | -1 mod n | ||
|---|---|---|---|
| 2 | 1 | 1 | 1 |
| 3 | 2 | 2 | 2 |
| 4 | 6 | 2 | 3 |
| 5 | 24 | 4 | 4 |
| 6 | 120 | 0 | 5 |
| 7 | 720 | 6 | 6 |
| 8 | 5040 | 0 | 7 |
| 9 | 40320 | 0 | 8 |
| 10 | 362880 | 0 | 9 |
| 11 | 3628800 | 10 | 10 |
| 12 | 39916800 | 0 | 11 |
| 13 | 479001600 | 12 | 12 |
| 14 | 6227020800 | 0 | 13 |
| 15 | 87178291200 | 0 | 14 |
| 16 | 1307674368000 | 0 | 15 |
| 17 | 20922789888000 | 16 | 16 |
| 18 | 355687428096000 | 0 | 17 |
| 19 | 6402373705728000 | 18 | 18 |
| 20 | 121645100408832000 | 0 | 19 |
| 21 | 2432902008176640000 | 0 | 20 |
| 22 | 51090942171709440000 | 0 | 21 |
| 23 | 1124000727777607680000 | 22 | 22 |
| 24 | 25852016738884976640000 | 0 | 23 |
| 25 | 620448401733239439360000 | 0 | 24 |
| 26 | 15511210043330985984000000 | 0 | 25 |
| 27 | 403291461126605635584000000 | 0 | 26 |
| 28 | 10888869450418352160768000000 | 0 | 27 |
| 29 | 304888344611713860501504000000 | 28 | 28 |
| 30 | 8841761993739701954543616000000 | 0 | 29 |
Demostración[editar]
Usando aritmética modular[editar]
De derecha a izquierda[editar]
Por contradicción. Suponga que y no es primo. Dado que no es primo, existe tal que , es decir, . Además, no es difícil ver que . Si escribimos entonces, a partir de la hipótesis se concluye que
Además, aprovechando el hecho de que se deduce que y luego Vemos que tiene inverso en módulo , lo cual no puede ser cierto pues Esta contradicción proviene de suponer que no es primo.
De izquierda a derecha[editar]
Sea un número primo. Dado que es primo, entonces para todo se tiene que y entonces cada tiene un único inverso módulo en el conjunto .
Para ver que es único, supongamos tales que y . Luego se tiene , de donde
De lo anterior se colige que Además, del supuesto se tiene que Sin embargo, para cada se tiene que , es decir, , lo cual es una contradicción. Lo mismo ocurre si Vemos entonces que , lo que garantiza la unicidad.
Ahora, es claro que son inversos de sí mismos en módulo , y para todo otro elemento en se tiene un inverso en módulo diferente al de los demás (por la unicidad). Así, podemos agrupar cada elemento con su inverso, de modo que
De aquí, multiplicando a ambos lados por se concluye , lo que finaliza la demostración.
Usando teoría de grupos[editar]
Esta demostración usa el hecho de que si p es un número primo, entonces el conjunto de números G = (Z/pZ)× = {1, 2, ... p − 1} forma un grupo bajo la multiplicación. Esto significa que para cada elemento a de G, hay un único inverso multiplicativo b en G tal que ab ≡ 1 (mod p). Si a ≡ b (mod p), entonces a2 ≡ 1 (mod p), que se puede factorizar en a2 − 1 = (a + 1)(a − 1) ≡ 0 (mod p), y puesto que p es primo, entonces a ≡ 1 o −1 (mod p), por ejemplo a = 1 o a = p − 1.
En otras palabras, 1 y p − 1 son cada uno su propio inverso, pero para cualquier otro elemento de G hay un inverso, también en G, así que si tomamos todos los elementos de G por parejas y los multiplicamos todos ellos juntos, el producto será igual a −1 (módulo p). Por ejemplo, si p = 11, tenemos que:
Las propiedades conmutativas y asociativas son usadas en el procedimiento de arriba. Todos los elementos en el producto anterior serán de la forma g g −1 ≡ 1 (mod p) excepto 1 (p − 1), que están al principio del producto.
Si p = 2, el resultado es trivial e inmediato.
Para demostrar el inverso del teorema (ver siguiente sección), supóngase que la congruencia se cumple para un número compuesto n, nótese entonces que n tiene un divisor propio d con 1 < d < n. Claramente, d divide a (n − 1)! pero por la congruencia, d también divide a (n − 1)! + 1, así que d divide a 1, con lo que se llega a una contradicción.
Usando polinomios[editar]
Sea p un número primo. Consideremos el polinomio
Recordemos que si f(x) es un polinomio no nulo de grado d sobre un cuerpo F, entonces f(x) tiene un máximo de d raíces en F, y recordemos que el conjunto de todos los restos módulo un primo, con las operaciones de suma y multiplicación, es un cuerpo. Ahora, siendo g(x)
Puesto que los coeficientes de mayor orden se cancelan, f(x) es un polinomio de grado p − 2 como mucho. Por tanto, si tomamos restos módulo p, f(x) tendrá a lo sumo p − 2 raíces módulo p. Sin embargo, a la vista de la definición de f(x), del pequeño teorema de Fermat se sigue que cada elemento 1, 2, ..., p − 1 es una raíz de f(x) (por lo que, a fortiori, es una raíz de f(x) módulo p). Esto es imposible a menos que f(x) sea idénticamente cero módulo p, esto es, a menos que cada coeficiente de f(x) sea divisible por p.
Dado que el término constante de f(x) es justamente (p − 1)! + 1,
Inverso[editar]
El inverso del teorema de Wilson dice que para cualquier número compuesto n > 5,
- n divide a (n − 1)!.
Se deja el caso n = 4, para el cual 3! no es divisible por 4 (es únicamente divisible por 2).
En efecto, si q es un factor primo de n, de tal manera que n = qa, los números
- 1, 2, ..., n − 1
incluyendo a − 1 múltiplos de q. Por lo tanto, las potencias de q que dividen al factorial son al menos n/q − 1; y las potencias que dividen a n son a lo máximo
- log n/log q.
La inecuación
- log n/log q ≤ n/q − 1
se cumple en general, excepto para el caso q = 2 y n = 4.
Test de primalidad[editar]
El teorema de Wilson no se utiliza como test de primalidad en la práctica, ya que para calcular (n − 1)! modulo npara un número n grande es costoso (computacionalmente hablando), y se conocen tests más sencillos y rápidos.
Usando el teorema del Wilson, se tiene que para cada número primo p:
donde p = 2n + 1. Esto se convierte en
Así, la primalidad del número se determina mediante los residuos cuadráticos de p. Esto se puede usar de hecho para probar parte de otro famoso resultado: −1 es un cuadrado (residuo cuadrático) mod p si p ≡ 1 (mod 4). Para la suposición, p = 4k + 1 para algún entero k. Entonces, tomando n = 2k y sustituyendo, se concluye que:
El teorema de Wilson ha sido utilizado para generar fórmulas para los primos, pero es demasido lento como para tener valor práctico.
Generalización[editar]
El teorema de Wilson se puede generalizar, como mostró Carl Friedrich Gauss en su libro Disquisitiones Arithmeticae:
donde p es un número primo impar, y k pertenece a los números naturales, es decir, . El teorema se generaliza más por el hecho de que en cualquier grupo abeliano finito, ya sea el producto de todos los elementos es la identidad, o precisamente hay un elemento a de orden 2. En este último caso, el producto de todos los elementos es igual a.
No hay comentarios:
Publicar un comentario