ÁLGEBRA

ARITMÉTICA MODULAR

teorema chino del resto es un resultado sobre congruencias en teoría de números y sus generalizaciones en álgebra abstracta. Fue publicado por primera vez en el siglo III por el matemático chino Sun Tzu.

Enunciado del teorema[editar]

Supongamos que n₁, n₂, …, n_k son enteros positivos coprimos dos a dos. Entonces, para enteros dados a₁,a₂, …, a_k, existe un entero x que resuelve el sistema de congruencias simultáneas

${\displaystyle {\begin{aligned}x&\equiv a_{1}{\pmod {n_{1}}}\\x&\equiv a_{2}{\pmod {n_{2}}}\\&\vdots \\x&\equiv a_{k}{\pmod {n_{k}}}\end{aligned}}}$

Más aún, todas las soluciones x de este sistema son congruentes módulo el producto ${\displaystyle N=n_{1}n_{2}...n_{k}}$.

De manera más general, las congruencias simultáneas pueden ser resueltas si los n_i's son coprimos a pares. Una solución x existe si y solo si:

${\displaystyle a_{i}\equiv a_{j}{\pmod {\operatorname {mcd} (n_{i},n_{j})}}\qquad {\text{para todo }}i\ {\text{y }}j.\,\!}$

Todas las soluciones x son entonces congruentes módulo el mínimo común múltiplo de los n_i.

Un enunciado moderno en lenguaje algebraico es que para cada entero positivo con factorización en números primos

${\displaystyle n=p_{1}^{r_{1}}\cdots p_{k}^{r_{k}},}$

se tiene un isomorfismo entre un anillo y la suma directa de sus potencias primas¹​

${\displaystyle \mathbf {Z} /n\mathbf {Z} \cong \mathbf {Z} /p_{1}^{r_{1}}\mathbf {Z} \oplus \cdots \oplus \mathbf {Z} /p_{k}^{r_{k}}\mathbf {Z} .}$

Demostración del teorema[editar]

Existencia de la solución[editar]

Sea N=n₁n₂...n_k y sea ${\displaystyle N_{i}={\frac {N}{n_{i}}}}$ para i=1,...,k. Como todos los módulos n_i son coprimos entre sí, N_i y n_i son a su vez coprimos entre sí, luego por la Identidad de Bezout se asegura la existencia de dos enteros r_i y s_i tales que ${\displaystyle r_{i}n_{i}+s_{i}N_{i}=1}$. En tales condiciones, tomando las clases de equivalencia en ambos lados de la identidad, se tiene que para cada i, y para cada j ≠ i:

${\displaystyle {\begin{aligned}s_{i}N_{i}\equiv 1{\pmod {n_{i}}}\\s_{i}N_{i}\equiv 0{\pmod {n_{j}}}\\\end{aligned}}}$

Por tanto, definiendo

${\displaystyle x:=\sum _{i=1}^{k}a_{i}s_{i}N_{i}=a_{1}s_{1}N_{1}+a_{2}s_{2}N_{2}+\ldots +a_{k}s_{k}N_{k},}$

es claro que x es la solución buscada, debido a que al tomar clases de equivalencia en cada n_i, todos los sumandos se anulan a excepción del propio a_is_iN_i, y por tanto, ${\displaystyle x\equiv a_{i}{\pmod {n_{i}}}}$ para todo i =1,...,k. De esta manera, queda demostrado que x es solución del sistema.

Unicidad de la solución[editar]

En el caso de que todos los n_i sean coprimos, esa solución es la única existente módulo N. Para demostrarlo, supongamos que existiesen dos números enteros x e y que son soluciones distintas, entonces para i =1,2,...,k:

${\displaystyle {\begin{aligned}x\equiv a_{i}{\pmod {n_{i}}}\\y\equiv a_{i}{\pmod {n_{i}}}\\\end{aligned}}}$

Esto implica que ${\displaystyle x-y\equiv 0{\pmod {n_{i}}}}$, y por ser todos los n_i coprimos, se sigue que el producto de los módulos N=n₁n₂...n_k también divide a x - y, es decir, ${\displaystyle x\equiv y{\pmod {N}}}$.

Por tanto, toda solución del sistema es congruente con x en módulo N, tal y como se había establecido previamente en la formulación del teorema.

Historia[editar]

La forma original del teorema, contenida en un libro del siglo III por el matemático chino Sun Tzu²​³​ y posteriormente publicado en 1247 por Qin Jiushao, es un enunciado sobre congruencias simultáneas (ver aritmética modular).

Versiones del teorema chino del resto fueron también conocidas por Brahmagupta, y aparecen en el Liber Abacide Fibonacci (1202).

Aplicaciones[editar]

El teorema chino del resto tiene importantes aplicaciones en criptografía, en especial para reducir operaciones con números enormes mediante el paso a congruencias. En el algoritmo RSA, por ejemplo, los cálculos se hacen módulo ${\displaystyle n}$, donde ${\displaystyle n}$ es un producto de dos primos ${\displaystyle p}$ y ${\displaystyle q}$. Tamaños habituales para ${\displaystyle n}$ son 1024, 2048 ó 4096 bits, haciendo que los cálculos requieran una gran cantidad de tiempo. Usando el teorema chino del resto los cálculos pueden ser transportados del anillo ${\displaystyle \mathbf {Z} _{n}}$ al anillo ${\displaystyle \mathbf {Z} _{p}\times \mathbf {Z} _{q}}$. La suma de las longitudes de bit de ${\displaystyle p}$ y ${\displaystyle q}$ es la longitud de bit de ${\displaystyle n}$, haciendo ${\displaystyle p}$ y ${\displaystyle q}$ considerablemente menor que ${\displaystyle n}$. Esto acelera mucho los cálculos. Nótese que las implementaciones del algoritmo RSA usando el teorema chino del resto son más susceptibles a ataques de "fault injection".

pequeño teorema de Fermat, que establece:

Si a es un número natural y p un número primo, entonces ${\displaystyle a^{p}\equiv a{\pmod {p}}}$.

Este teorema es un caso especial del teorema de Euler que generaliza este concepto mucho más.

Demostración original de Euler[editar]

Leonhard Euler dio en 1736 la primera demostración en un artículo titulado Theorematum Quorundam ad Números Primos Spectantium Demonstratio¹​ y es la siguiente:

Se demuestra por inducción matemática sobre los números naturales.

Sea n = 1, sabemos que 1^p -1 = 0 es divisible por p primo. Supongamos ahora que se aplica para 2 y es correcto, entonces tendremos que p|2^p -2. Si se aplica a todos los números hasta n y se cumple la proposición, y se puede demostrar que para n + 1 también se cumple, entonces se cumplirá para todo n.

• Partimos de que ${\displaystyle p\mid n^{p}-n\,\!}$

• Utilizamos el binomio de Newton para expandir la potencia (n + 1)^p:

${\displaystyle (n+1)^{p}=\sum _{k=0}^{p}\left({\frac {p!}{k!(p-k)!}}\right)n^{p-k}}$

• Agrupando factores y reordenando la identidad:

${\displaystyle (n+1)^{p}-(n+1)=n^{p}-n+\sum _{k=1}^{p-1}\left({\frac {p!}{k!(p-k)!}}\right)n^{p-k}}$

• Dado que el número resultante del sumatorio del miembro de la derecha es divisible por p, porque el coeficiente binomial ${\displaystyle {\frac {p!}{k!(p-k)!}}}$ es divisible por p para 0 < k < p y p primo, y n^p -n es divisible por p por hipótesis inductiva, tenemos que (n + 1)^p -(n + 1) es divisible por p.

• Repitiendo el proceso vemos que se cumple para todo n.

Demostración usando el teorema de Euler[editar]

El pequeño teorema de Fermat se puede demostrar como un caso particular del teorema de Euler. Si a es un número coprimo con n, entonces:

${\displaystyle a^{\varphi (n)}\equiv 1{\pmod {n}}}$

donde φ(n) es la función φ de Euler. Dado que para cada primo p, φ(p) = p - 1, entonces obtenemos que

${\displaystyle a^{p-1}\equiv 1{\pmod {p}}}$

que es la forma en la que se suele representar el teorema. Para obtener la forma original, solo debemos conocer una sencilla propiedad en aritmética modular que dice que si A, B son dos números enteros cualesquiera tales que A ≡ B (mod n), entonces para cualquier número natural C tenemos que AC ≡ BC (mod n).

Multiplicando a en ambos lados de la relación de equivalencia obtenemos la forma original:

${\displaystyle a^{p}\equiv a{\pmod {p}}}$

Demostración utilizando aritmética modular[editar]

Esta demostración²​ se basa en el uso de aritmética modular y es la que suele aparecer en los textos de teoría de números. La demostración se basa en dos lemas que se exponen a continuación:

Lema 1: Ley de cancelación.

Si u, x e y son números enteros y u no es divisible por un número primo p, y

${\displaystyle ux\equiv uy{\pmod {p}}\,\!}$

entonces nosotros podemos "cancelar" u, quedando

${\displaystyle x\equiv y{\pmod {p}}.\,\!}$

Se puede comprobar fácilmente esto ya que según el lema de Euclides, si un primo p divide al producto rs(donde r y s son enteros), entonces p divide a r o p divide a s. Dado que ux ≡ uy (mod p) significa que p divide a ux - uy, sacando factor común, u(x - y), y puesto que p no divide a u, tenemos que p divide a (x - y) de lo que se sigue que x ≡ y (mod p).

Lema 2: Propiedad de reagrupación.

La secuencia

${\displaystyle a,2a,3a,\ldots ,(p-1)a,\,\!}$

con a no divisible por p, cuando es reducida módulo p , puede volver a reagruparse en la secuencia

${\displaystyle 1,2,3,\ldots ,p-1.\,\!}$

Para empezar, ninguno de los términos a, 2a, ..., (p − 1)a puede ser cero módulo p, ya que si k es uno de los números 1, 2, ..., p − 1, entonces k no es divisible por p, y tampoco a, así que, según el lema de Euclides ka no es divisible por p. Por lo tanto, los números de la secuencia a, 2a, ..., (p − 1)a, al ser reducidos módulo p, deben encontrarse entre los números 1, 2, 3, ..., p − 1.

Ahora bien, los números a, 2a, ..., (p − 1)a deben de ser todos distintos al ser reducidos módulo p, puesto que si

${\displaystyle ka\equiv ma{\pmod {p}}\,\!}$

donde k y m son números de la lista 1, 2, ..., p − 1, entonces la ley de cancelación dice que

${\displaystyle k\equiv m{\pmod {p}}.\,\!}$

Al reducir la secuencia a, 2a, ..., (p − 1)a módulo p, obtendremos la secuencia 1, 2, ..., p − 1, pero en distinto orden, en definitiva, una biyección.

Demostración.

• Sea a un entero positivo no divisible por p. Escribimos la secuencia de números

${\displaystyle a,2a,3a,\ldots ,(p-1)a}$

• Si se reduce cada elemento de la secuencia módulo p y se reagrupa (lema 2), nos queda la secuencia:

${\displaystyle 1,2,3,\ldots ,(p-1)}$

• Multiplicando todos los elementos de la primera secuencia, se observa que es equivalente módulo p a la multiplicación de todos los elementos de la segunda secuencia, o sea:

${\displaystyle a\cdot 2a\cdot 3a\cdot \cdots \cdot (p-1)a\equiv 1\cdot 2\cdot 3\cdot \cdots (p-1){\pmod {p}}.}$

• Agrupando los términos a:

${\displaystyle a^{p-1}(1\cdot 2\cdot 3\cdot \cdots \cdot (p-1))\equiv 1\cdot 2\cdot 3\cdot \cdots (p-1){\pmod {p}}.}$

• Finalmente, cancelando (lema 1) los números 1, 2 , ..., p - 1 obtenemos:

${\displaystyle a^{p-1}\equiv 1{\pmod {p}}.\,\!}$

Demostración utilizando teoría de grupos[editar]

Esta demostración requiere los más básicos elementos de teoría de grupos.

La idea fundamental es reconocer que el grupo G={1, 2, …, p − 1}, con la operación de multiplicación (bajo módulo p) forma un grupo. Generalmente se denota a este grupo como (Z/nZ)^x. El único axioma de grupo que requiere un poco esfuerzo de demostrar es que cada elemento de G es invertible. Se demuestra a continuación.

Propiedad de invertibilidad.

Para demostrar que cada elemento b de G es invertible, se procede de la siguiente manera. Puesto que b es coprimo con p, la identidad de Bézout asegura que existen dos enteros x e y tales que:

${\displaystyle bx+py=1\,\!}$

Leyendo esta ecuación "módulo p", se puede observar que x es el inverso de b (módulo p), puesto que

${\displaystyle bx\equiv 1{\pmod {p}}\,\!}$

Como para cada b ∈ G existe un x que es su inverso módulo p, de concluye que G es un grupo.

Una vez demostrado que G es un grupo se demuestra el teorema:

• Sea a un número entre 1 ≤ a ≤ p − 1, esto es, un elemento de G. Sea k el orden de a, así pues

${\displaystyle a^{k}\equiv 1{\pmod {p}}\,\!}$

• Por el teorema de Lagrange, k divide el orden de G, que es p - 1, así que p - 1=km para algún entero m. Luego

${\displaystyle a^{p-1}\equiv a^{km}\equiv (a^{k})^{m}\equiv 1^{m}\equiv 1{\pmod {p}}\,\!}$

Si  es un número primo, entonces para cada número  el número    es divisible en .

Ejemplo: Tomamos  un número primo, entonces  es divisible en  sea  un número entero cualquiera (positivo, negativo o cero).

Fermat sostenía que tenía una demostración del teorema, pero según le cuenta a Frenicle de Bessy, esta era demasiado extensa para incluirla en la carta. El primero en demostrar el teorema fue Gottfried Leibniz en un manuscrito en 1683 que no llegó a publicar. La primera demostración publicada, casi cien años después, es de Leonhard Euler, quien en 1736 la presentó en un artículo titulado Theorematum Quorundam ad Numeros Primos Spectantium Demonstratio.

Hasta los inicios del siglo XX este teorema era conocido como “teorema de Fermat” , en 1913 el matemático Kurt Hensel en su libro Zahlentheorie lo rebautiza como “pequeño teorema de Fermat” tal como se conoce actualmente.

Si bien parace que demostrar este teorema requiere de una matemática avanzada, es sorprendente encontrar que puede demostrarse de manera sencilla y directa utilizando nada más que inducción matemática y el teorema del binomio.

A continuación el desarrollo la demostración:

(1) Sea  un número primo:

• Si    divisible en 
• Si    divisible en 

(2) Suponemos que si para todos los valores positivos de  tenemos que  es divisible en por inducción matemática la hipótesis es válida también para , entonces tenemos que:

•  es divisible en 
•  es divisible en 

Por Teorema del Binomio sabemos que:

Hacemos pasaje de términos y obtenemos:

   (1)

En el lado derecho de la ecuación (1) encontramos que cada coeficiente  con  es divisible en . Por la propia definición de  tenemos que:

  aquí  divide la parte derecha de la ecuación. Para todos los coeficientes de la expresión,  es un valor menor a , entoces el factor primo  no ocurre en el producto  , por lo tanto  divide a .

Entonces como  divide a cada coeficiente del lado derecho de la ecuación (1), debe dividir también a la expresión completa del lado derecho y consecuentemente divide también el lado izquierdo .

A partir de la hipótesis inductiva que  divide a , tenemos que:

•   

•   

Por lo  tanto por inducción matemática la hipótesis es valida para todos los valores positivos de .

(3) La demostración se completa considerando los valores negativos de . Entonces definimos a los valores negativos de  como  .

– Si  es igual a  , tenemos que:

Los factores  y  son consecutivos, entonces uno de ellos es par y su producto divisible en .

– Si  es impar:

Sabemos que si  es positivo divide a , por lo tanto tambien divide a .

https://cosas.wordpress.com/2014/05/07/el-pequeno-teorema-de-fermat-una-demostracion-directa-y-simple/