Teorema de euler

format_list_bulleted Contenido keyboard_arrow_down

ImprimirCitar

Teorema sobre exponenciación modular

En teoría de números, Teorema de Euler (también conocido como Fermat-Euler theorem o Teorema totiente de Euler) declara que, si $n$ y $a$ son enteros positivos coprime, y $varphi (n)$ es la función totiente de Euler, entonces $a$ elevado al poder $varphi (n)$ es congruente con $1$ modulo $n$ ; eso es

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

En 1736, Leonhard Euler publicó una prueba del pequeño teorema de Fermat (enunciado por Fermat sin prueba), que es la restricción del teorema de Euler al caso donde $n$ es un número primo. Posteriormente, Euler presentó otras demostraciones del teorema, culminando con su artículo de 1763, en el que demostró una generalización al caso donde $n</span$ no es primo.

El contrario del teorema de Euler también es cierto: si la congruencia anterior es verdadera, entonces $a$ y $n$ Debe ser coprime.

El teorema se generaliza aún más mediante el teorema de Carmichael.

El teorema se puede utilizar para reducir fácilmente el modulo de grandes potencias $n$ . Por ejemplo, considere encontrar los que colocan dígitos decimales ${displaystyle 7^{222}}$ , es decir. ${displaystyle 7^{222}{pmod {10}}}$ . Los enteros 7 y 10 son coprime, y ${displaystyle varphi (10)=4}$ . Así que el teorema de Euler produce ${displaystyle 7^{4}equiv 1{pmod {10}}}$ , y tenemos ${displaystyle 7^{222}equiv 7^{4times 55+2}equiv (7^{4})^{55}times 7^{2}equiv 1^{55}times 7^{2}equiv 49equiv 9{pmod {10}}}$ .

En general, al reducir un poder $a$ modulo $n$ (donde) $a$ y $n$ son coprime), uno necesita trabajar modulo $varphi (n)$ en el exponente de $a$ :

x equiv y pmod{varphi(n)}

, entonces

a^x equiv a^y pmod{n}

El teorema de Euler subyace en el criptosistema RSA, que se usa ampliamente en las comunicaciones por Internet. En este criptosistema, el teorema de Euler se usa con $n$ siendo un producto de dos grandes números primos, y la seguridad de el sistema se basa en la dificultad de factorizar dicho número entero.

Pruebas

1. El teorema de Euler se puede probar usando conceptos de la teoría de grupos: Las clases de residuos módulo $n$ que son coprimos con $n$ forman un grupo bajo la multiplicación (ver el artículo Grupo multiplicativo de enteros módulo n para más detalles). El orden de ese grupo es $φ (n)$ . El teorema de Lagrange establece que el orden de cualquier subgrupo de un grupo finito divide el orden de todo el grupo, en este caso $φ (n)$ . Si $a$ es cualquier número coprimo de $n$ entonces $a$ está en una de estas clases de residuos, y sus poderes $a, a 2,... a k$ modulo $n$ forman un subgrupo del grupo de clases de residuos, con $a k \equiv 1 (mod n)$ . El teorema de Lagrange dice que $k$ debe dividir $φ (n)$ , es decir, hay un número entero $M$ tal que $kM = φ (n)$ . Esto implica entonces,

{displaystyle a^{varphi (n)}=a^{kM}=(a^{k})^{M}equiv 1^{M}=1equiv 1{pmod {n}}.}

2. También hay una demostración directa: Sea $R = {x 1, x 2,... x φ (n)}$ ser un sistema de residuos reducido ( $mod n$ ) y dejar que $a$ sea cualquier número entero coprimo de $n$ . La prueba depende del hecho fundamental de que la multiplicación por $a$ permuta el $x i$ : en otras palabras, si $ax j \equiv ax k (modificación n)$ luego $j = k$ . (Esta ley de cancelación se demuestra en el artículo Grupo multiplicativo de enteros módulo n.) Es decir, los conjuntos $R$ y $aR = {hacha 1, hacha 2,... ax φ (n)}$ , considerados como conjuntos de clases de congruencia ( $mod n$ ), son idénticos (como conjuntos; pueden estar enumerados en diferentes órdenes), por lo que el producto de todos los números en $R$ es congruente ( $mod n$ ) al producto de todos los números en $aR$ :

{displaystyle prod _{i=1}^{varphi (n)}x_{i}equiv prod _{i=1}^{varphi (n)}ax_{i}=a^{varphi (n)}prod _{i=1}^{varphi (n)}x_{i}{pmod {n}},}

y usando la ley de cancelación para cancelar cada

x i

da el teorema de Euler:

a^{varphi(n)}equiv 1 pmod{n}.

Contenido relacionado

Más resultados...