Teorema de Euler (teoría de números)

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 6 de mayo de 2022; la verificación requiere 1 edición .

El teorema de Euler en teoría de números dice:

Si y son coprimos , entonces , ¿dónde está la función de Euler ? $a$ $metro$ $a^{\varphi(m)} \equiv 1 \pmod m$ $\varfi(m)$

Una consecuencia importante del teorema de Euler para el caso de un módulo primo es el pequeño teorema de Fermat :

Si no es divisible por un número primo , entonces . $a$ $pags$ $a^{{p-1}}\equiv 1{\pmod p}$

A su vez, el teorema de Euler es una consecuencia del teorema algebraico general de Lagrange , aplicado al sistema reducido de residuos módulo . $metro$

Evidencia

Usando la teoría de números

Sean todos los números naturales distintos menores y primos relativos a él. $x_1, \puntos, x_{\varphi(m)}$ $metro$

Considere todos los productos posibles para todos desde hasta . $x_i un$ $i$ $una$ $\varfi(m)$

Dado que es coprimo con y coprimo con , entonces también es coprimo con , es decir, para algunos . $a$ $metro$ $x_{yo}$ $metro$ $x_i un$ $metro$ $x_i a \equiv x_j\pmod m$ $j$

Tenga en cuenta que todos los residuos cuando se dividen por son diferentes. De hecho, incluso si esto no es así, entonces hay tales que $x_i un$ $metro$ $i_1\neq i_2$

x_{i_1} a \equiv x_{i_2} a\pmod m

(x_{i_1} - x_{i_2}) a \equiv 0\pmod m.

Como coprimo con , la última igualdad es equivalente al hecho de que $a$ $metro$

x_{i_1} - x_{i_2} \equiv 0\pmod m

o .

x_{i_1} \equiv x_{i_2}\pmod m

Esto contradice el hecho de que los números son módulos distintos por pares . $x_1, \puntos, x_{\varphi(m)}$ $metro$

Multiplicamos todas las comparaciones de la forma . Obtenemos: $x_i a \equiv x_j\pmod m$

x_1 \cdots x_{\varphi(m)} a^{\varphi(m)} \equiv x_1 \cdots x_{\varphi(m)}\pmod m

x_1 \cdots x_{\varphi(m)} (a^{\varphi(m)}-1) \equiv 0\pmod m

Dado que el número es coprimo con , la última comparación es equivalente al hecho de que $x_1 \cdots x_{\varphi(m)}$ $metro$

a^{\varphi(m)}-1 \equiv 0\pmod m

a^{\varphi(m)} \equiv 1\pmod m.

■

Con la ayuda de la teoría de grupos

Considere el grupo multiplicativo de elementos invertibles $\mathbb Z_n^*$ del anillo residual . Su orden es igual según la definición de la función de Euler . Dado que el número es coprimo con , el elemento correspondiente en es invertible y pertenece a . El elemento genera un subgrupo cíclico cuyo orden, según el teorema de Lagrange , divide , por tanto, . ■ $\mathbb Z_n$ $\varfi (n)$ $a$ $norte$ $\overline un$ $\mathbb Z_n$ $\mathbb Z_n^*$ $\overline{a}\en \mathbb Z_n^*$ $\varfi (n)$ $\overline a^{{\varphi (n)}}=\overline 1$

Véase también

Lista de objetos que llevan el nombre de Leonhard Euler

Literatura

Ireland K., Rosen M. Una introducción clásica a la teoría de números moderna. — M .: Mir, 1987.

Enlaces

Temas: Teorema de Euler, Teorema del resto chino , Amir Kamil, CS70, otoño de 2003. UC Berkeley
RSA y el teorema del resto chino / Matemáticas discretas para CS Conferencia 12, Wagner, CS70, otoño de 2003. UC Berkeley