Teorema de Euler

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:

Si a y n son enteros primos relativos, entonces n divide al entero a^φ(n)- 1

sin embargo, es más común encontrarlo con notación moderna en la siguiente forma:

Si a y n son enteros primos relativos, entonces a^φ(n) ≡ 1 (mod n).

donde φ(n) es la función φ de Euler.

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 función φ de Euler. Tal función es multiplicativa: si m y n son primos relativos, entonces

Demostracion: Sabemos que:

de manera que:

Como ${displaystyle operatorname {mcd} (m,n)=1}$, ninguno de los primos ${displaystyle p_{i}}$ y ${displaystyle q_{i}}$ son iguales, luego la descomposición en primos de ${displaystyle mn}$ no se ve alterada, es decir, si ${displaystyle m=q_{1}^{eta _{1}}q_{2}^{eta _{2}}...q_{k}^{eta _{1}}}$ y ${displaystyle n=p_{1}^{alpha _{1}}p_{2}^{alpha _{2}}...p_{j}^{alpha _{j}}}$ la descomposición en primos de ${displaystyle mn}$ sera ${displaystyle mn=q_{1}^{eta _{1}}q_{2}^{eta _{2}}...q_{k}^{eta _{1}}p_{1}^{alpha _{1}}p_{2}^{alpha _{2}}...p_{j}^{alpha _{j}}}$, lo cual implica

por lo tanto

si ${displaystyle m}$ y ${displaystyle n}$ son primos relativos.

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, b respecto 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):

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

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í:

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:

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:

La prueba original del teorema de Euler, en notación moderna, se desarrolla en los siguientes pasos.

Es importante recalcar que la cancelación solo 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) solo puede obtenerse debido a que a y n son primos relativos.

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

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

por lo que, multiplicando ambos lados de la ecuación por 5³:

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. Por 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.

El teorema de Euler es una generalización del teorema de Fermat que establece:

Si p es un número primo y a es un entero, entonces p divide al número a^p-1-1

Fermat estableció tal resultado en una carta a Frénicle de Bessy, pero como era usual en él, omitió la prueba del mismo:

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

Si p es un número primo y a es un entero no divisible por p, entonces a^{p - 1} ≡ 1 (mod p).

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.