Función de Euler

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 1 de octubre de 2021; las comprobaciones requieren 3 ediciones .

La función de Euler es una función aritmética multiplicativa cuyo valor es igual al número de números naturales que son menores y coprimos con él [1] . $\varfi (n)$ $norte$

Por ejemplo, para el número 36 hay 12 números menores y coprimos (1, 5, 7, 11, 13, 17, 19, 23, 25, 29, 31, 35), entonces . ${\ estilo de visualización \ varphi (36) = 12}$

Nombrado en honor a Euler , quien lo utilizó por primera vez en 1763 en su trabajo sobre teoría de números para demostrar el pequeño teorema de Fermat , y luego para demostrar una afirmación más general: el teorema de Euler . La función fue utilizada más tarde por Gauss en sus Investigaciones aritméticas , publicadas en 1801. Gauss introdujo la notación ahora estándar [2] . $\varfi (n)$

La función de Euler encuentra aplicación en asuntos relacionados con la teoría de la divisibilidad y los residuos (ver comparación de módulos ), teoría de números , criptografía . La función de Euler juega un papel clave en el algoritmo RSA [3] .

Cálculo

Los primeros 99 valores de la función de Euler [4]

$\varfi (n)$	+0	+1	+2	+3	+4	+5	+6	+7	+8	+9
0+		una	una	2	2	cuatro	2	6	cuatro	6
10+	cuatro	diez	cuatro	12	6	ocho	ocho	dieciséis	6	Dieciocho
20+	ocho	12	diez	22	ocho	veinte	12	Dieciocho	12	28
30+	ocho	treinta	dieciséis	veinte	dieciséis	24	12	36	Dieciocho	24
40+	dieciséis	40	12	42	veinte	24	22	46	dieciséis	42
50+	veinte	32	24	52	Dieciocho	40	24	36	28	58
60+	dieciséis	60	treinta	36	32	48	veinte	66	32	44
70+	24	70	24	72	36	40	36	60	24	78
80+	32	54	40	82	24	64	42	56	40	88
90+	24	72	44	60	46	72	32	96	42	60

Información general

La función de Euler muestra cuántos números naturales del intervalo c tienen solo un divisor común: uno. La función de Euler se define sobre el conjunto de los números naturales , y sus valores se encuentran en el conjunto de los números naturales. $\varfi (n)$ $[1,\;n-1]$ $norte$

Como se deduce de la definición, para calcular , debe revisar todos los números desde hasta , y para cada uno verificar si tiene divisores comunes con , y luego calcular cuántos números resultaron ser coprimos con . Este procedimiento para números grandes requiere mucho tiempo, por lo tanto , se utilizan otros métodos para el cálculo , que se basan en las propiedades específicas de la función de Euler. $\varfi (n)$ $una$ $n-1$ $norte$ $norte$ $norte$ $\varfi (n)$

La tabla de la derecha muestra los primeros 99 valores de la función de Euler. Al analizar estos datos, puede ver que el valor no excede y es exactamente igual a if - prime. Por lo tanto, si se dibuja una línea en coordenadas , los valores estarán en esta línea o debajo de ella. Además, mirando el gráfico al comienzo del artículo y los valores en la tabla, podemos suponer que hay una línea recta que pasa por cero, que limita los valores desde abajo. Sin embargo, resulta que tal línea no existe. Es decir, no importa cuán plana sea la línea recta que dibujemos, siempre habrá un número natural tal que se encuentre debajo de esta línea recta. Otra característica interesante del gráfico es la presencia de unas líneas rectas a lo largo de las cuales se concentran los valores de la función de Euler. Entonces, por ejemplo, además de la línea en la que se encuentran los valores , donde es un primo, se distingue una línea que corresponde aproximadamente a , en la que caen los valores , donde es un primo. $\varfi (n)$ $n-1$ $norte$ $(Nueva York)$ $y=n-1$ $y=\varfi(n)$ $\varfi (n)$ $norte$ $\varfi (n)$ $y=n-1$ $\varphi(n)=n-1$ $norte$ $y=n/2$ $\varphi(2n)=\varphi(n)=n-1$ $norte$

El comportamiento de la función de Euler se analiza con más detalle en la sección #Relaciones asintóticas .

Multiplicatividad de la función de Euler

Una de las principales propiedades de la función de Euler es su multiplicatividad . Esta propiedad fue establecida por Euler y se formula de la siguiente manera: para cualquier número coprimo y [5] $metro$ $norte$

\varphi(mn)=\varphi(m)\varphi(n).

Prueba de multiplicatividad

Para probar la multiplicatividad de la función de Euler, necesitamos el siguiente teorema auxiliar [6] .

Teorema 1. Sea y recorre el sistema completo de residuos módulo , mientras recorre el sistema completo de residuos módulo . Entonces los números forman un sistema completo de residuos módulo .

(m,\;m')=1

a

metro

a'

metro'

soy + soy

metro

metro'

Prueba. si un

a_1'm+a_1m'\equiv a_2'm+a_2m'\pmod{mm'},

después

a_1m'\equiv a_2m'\pmod m,

es por eso

a_1\equiv a_2\pmod m;

igualmente

a_1'\equiv a_2'\pmod{m'}.

Por lo tanto, existen números de módulo incomparables que forman un sistema completo de residuos de módulo .

mm'

mm'

Ahora podemos probar la afirmación principal [7] .

Teorema 2. La función de Euler es multiplicativa. Prueba. Si , entonces por el Teorema 1 pasa por el sistema reducido de residuos módulo , cuando y pasa por los sistemas reducidos de residuos módulo y respectivamente. También:

(m,\;m')=1

soy + soy

mm'

a

a'

metro

metro'

(soy+soy',\;mm')=1

\Leftrightarrow (a'm+am',\;m)=1,\;(a'm+am',\;m')=1

\Leftrightarrow (am',\;m)=1,\;(am,\;m')=1

\Leftrightarrow (a,\;m)=1,\;(a',\;m')=1.

Por lo tanto, los números que son menores que un número y son coprimos con él son los residuos positivos más pequeños entre los valores para los cuales son coprimos y coprimos con . De ahí se sigue que

\varphi(mm')

mm'

\varphi(m)\varphi(m')

soy + soy

a

metro

a'

metro'

\varphi(mm')=\varphi(m)\varphi(m').

La función de Euler de un número primo

Porque un valor simple de la función de Euler viene dado por una fórmula explícita [8] : $pags$

\varphi(p)=p-1,

que se sigue de la definición. De hecho, si es un primo, entonces todos los números menores que son coprimos, y hay exactamente uno de ellos. $pags$ $pags$ $p-1$

Para calcular la función de Euler de la potencia de un número primo, utilice la siguiente fórmula [8] :

\varphi(p^n)=p^np^{n-1}.

Esta igualdad se justifica de la siguiente manera. Contemos el número de números desde hasta que no son coprimos hasta . Todos ellos, obviamente, son múltiplos , es decir, se ven como: Total de tales números . Por lo tanto, el número de números coprimos con es igual a . $una$ $pag^{n}$ $pag^{n}$ $pags$ $p,\;2p,\;3p,\;\ldots,\;p^{n-1}p.$ $p^{n-1}$ $pag^{n}$ ${\displaystyle p^{n}-p^{n-1))$

La función de Euler de un número natural

El cálculo para un natural arbitrario se basa en la multiplicatividad de la función de Euler, la expresión para y también en el teorema fundamental de la aritmética . Para un número natural arbitrario, el valor se representa como [8] : $\varfi (n)$ $norte$ $\varphi(p^{n})$ $\varfi (n)$

\varphi(n)=n\prod_{p\mid n}\left(1-\frac{1}{p}\right),\;\;n>1,

donde es un número primo y recorre todos los valores involucrados en la descomposición en factores primos. $pags$ $norte$

Prueba

Como se desprende del teorema fundamental de la aritmética , cualquier número natural se representa de forma única en la forma: $n>1$

n=p_1^{\alpha_1}\cdot\ldots\cdot p_k^{\alpha_k},

donde son números primos y son números naturales. $p_1<\ldots<p_k$ $\alpha_1,\;\ldots,\;\alpha_k$

Usando la multiplicatividad de la función de Euler y la expresión para , obtenemos: $\varphi(p^{k})$ ${\begin{alineado}\varphi (n)&=\varphi (p_{1}^{\alpha _{1)))\varphi (p_{2}^{\alpha _{2))) \cdot \ldots \cdot \varphi (p_{k}^{\alpha _{k)))=\\&=p_{1}^{\alpha _{1))\left(1-{\frac { 1}{p_{1}}}\right)p_{2}^{\alpha _{2}}\left(1-{\frac {1}{p_{2}}}\right)\cdot \ldots \cdot p_{k}^{\alpha _{k}}\left(1-{\frac {1}{p_{k}}}\right)=\\&=p_{1}^{\alpha _ {1}}p_{2}^{\alpha _{2}}\cdot \ldots \cdot p_{k}^{\alpha _{k}}\left(1-{\frac {1}{p_{ 1}}}\right)\left(1-{\frac {1}{p_{2}}}\right)\cdot \ldots \cdot \left(1-{\frac {1}{p_{k} }}\right)=\\&=n\left(1-{\frac {1}{p_{1}}}\right)\left(1-{\frac {1}{p_{2}}} \right)\cdot \ldots \cdot \left(1-{\frac {1}{p_{k}}}\right).\end{alineado}}$

Ejemplo de aplicación: $\varphi (36)=\varphi (2^{2}\cdot 3^{2})=\varphi (2^{2})\varphi (3^{2})=(2^{2 }-2)(3^{2}-3)=2\cdot 6=12.$

Propiedades

Multiplicatividad generalizada

La función de Euler es una función aritmética multiplicativa , es decir

\varphi (mn)=\varphi (m)\varphi (n)\;\;\;\forall m,\,n\in \mathbb {N} \colon (m,\,n)=1 .

Es esencial aquí que el máximo común divisor y sea igual a uno. Resulta que hay una generalización de esta fórmula al caso cuando y tienen divisores comunes distintos de la unidad. Es decir, para cualquier natural y [9] : $metro$ $norte$ $metro$ $norte$ $metro$ $norte$

\varphi(m \cdot n) = \varphi(m) \cdot \varphi(n)\cdot\frac{d}{\varphi(d)},

donde es el máximo común divisor y Esta propiedad es una generalización natural de la multiplicatividad. $d$ $metro$ $norte.$

Prueba de multiplicatividad generalizada

Sea entonces y en el caso general y Por lo tanto, podemos escribir: ${\ estilo de visualización (m, \, n) = d,}$ $m = m'd, \; n = n'd,$ ${\ estilo de visualización (m', \, d) \ neq 1}$ ${\ estilo de visualización (n', \, d) \ neq 1.}$

d=d_{1}^{\delta _{1))\cdot \ldots \cdot d_{k}^{\delta_{k))\cdot d_{k+1}^{\delta _ {k+1}}\cdot \ldots \cdot d_{K}^{\delta _{K)),

m'=d_{1}^{\alpha _{1))\cdot \ldots \cdot d_{k}^{\alpha _{k))\cdot p_{1}^{\beta 1))\cdot \ldots \cdot p_{r}^{\beta _{r)),

n'=d_{k+1}^{\gamma _{k+1}}\cdot \ldots \cdot d_{K}^{\gamma_{K}}\cdot q_{1}^{ \varepsilon _{1}}\cdot \ldots \cdot q_{s}^{\varepsilon _{s}}.

Aquí los primeros divisores también son divisores y los últimos divisores son divisores Escribamos: $k$ $d$ $metro',$ $kk$ $d$ $norte'.$

\varphi (mn)=\varphi (d^{2}\cdot m'n')=\varphi ((d_{1}^{\delta _{1))\cdot \ldots \cdot d_{ k}^{\delta _{k}}\cdot d_{k+1}^{\delta _{k+1}}\cdot \ldots \cdot d_{K}^{\delta _{K}}) ^{2}\cdot d_{1}^{\alpha _{1}}\cdot \ldots \cdot d_{k}^{\alpha _{k}}\cdot p_{1}^{\beta_{ 1}}\cdot \ldots \cdot p_{r}^{\beta _{r}}\cdot d_{k+1}^{\gamma _{k+1}}\cdot \ldots \cdot d_{K }^{\gamma _{K}}\cdot q_{1}^{\varepsilon _{1}}\cdot \ldots \cdot q_{s}^{\varepsilon _{s}}).

Debido a la multiplicatividad de la función de Euler, y teniendo en cuenta también la fórmula

\varphi(p^n) = p^n(1-\frac{1}{p}),

donde es un primo, obtenemos: $pags$

{\begin{alineado}\varphi (mn)&=d_{1}^{\alpha _{1}+\delta _{1}}\left(1-{\frac {1}{d_{ 1}}}\right)\cdot \ldots \cdot d_{k}^{\alpha _{k}+\delta _{k}}\left(1-{\frac {1}{d_{k}} }\right)\cdot p_{1}^{\beta _{1}}\left(1-{\frac {1}{p_{1}}}\right)\cdot \ldots \cdot p_{r} ^{\beta _{r}}\left(1-{\frac {1}{p_{r}}}\right)\cdot d_{k+1}^{\delta _{k+1}}\ izquierda(1-{\frac {1}{d_{k+1}}}\derecha)\cdot \ldots \cdot d_{K}^{\delta _{K}}\izquierda(1-{\frac { 1}{d_{K))}\right)\times \\&\;\times \;d_{k+1}^{\gamma _{k+1}+\delta _{k+1}}\ izquierda(1-{\frac {1}{d_{k+1}}}\derecha)\cdot \ldots \cdot d_{K}^{\gamma_{K}+\delta_{K}}\izquierda (1-{\frac {1}{d_{K}}}\right)\cdot q_{1}^{\varepsilon _{1}}\left(1-{\frac {1}{q_{1} }}\right)\cdot \ldots \cdot q_{s}^{\varepsilon _{s}}\left(1-{\frac {1}{q_{s}}}\right)\cdot d_{1 }^{\delta _{1}}\left(1-{\frac {1}{d_{1}}}\right)\cdot \ldots \cdot d_{k+1}^{\delta_{k +1}}\left(1-{\frac {1}{d_{k+1}}}\right)\times \\&\;\times \;{\frac {1}{\left(1- {\frac {1}{d_{1}}}\right)\cdot \ldots \cdot \left(1-{\fr  ac {1}{d_{K}}}\right)}}.\end{alineado}}

La primera línea está escrita en la segunda, y la tercera se puede representar como Por lo tanto: $\varfi(m),$ $\varphi(n),$ $d/\varphi(d).$

\varphi(m \cdot n) = \varphi(m) \cdot \varphi(n) \cdot \frac{d}{\varphi(d)}.

Algunos casos especiales:

$\;\varphi\left(n^m\right) = n^{m-1}\varphi(n).$
$\varphi (2m)={\begin{casos}2\varphi (m),&m=2k,\;k\in \mathbb {N},\\\varphi (m),&m=2k-1 ,\;k\in \mathbb {N} .\end{casos}}$
$\varphi(M)\cdot\varphi(d) = \varphi(m)\cdot\varphi(n),$ donde es el mínimo común múltiplo de y , y es su máximo común divisor. $METRO$ $metro$ $norte$ $d$

Teorema de Euler

La propiedad establecida por Euler se usa con mayor frecuencia en la práctica :

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

si y son primos relativos . Esta propiedad, que se llama teorema de Euler , se deriva del teorema de Lagrange y del hecho de que es igual al orden del grupo multiplicativo de elementos invertibles del anillo de residuos módulo . Como consecuencia del teorema de Euler, se puede obtener el pequeño teorema de Fermat . Para hacer esto, debe tomar no de forma arbitraria sino simple. Después: $a$ $metro$
$\varfi(m)$ $metro$
$metro,$

a^{m - 1}\equiv 1\pmod m.

La última fórmula encuentra uso en varias pruebas de primalidad .

Otras propiedades

Con base en la representabilidad por el producto de Euler, es fácil obtener la siguiente declaración útil: $\varfi (n)$

a\mid b \Rightarrow \varphi(a)\mid\varphi(b).

La siguiente igualdad [10] [11] es una consecuencia del teorema de Zsigmondy :

\varphi (a^{n}+b^{n})\equiv 0{\pmod {n)),\;a>b\geqslant 1.

Cualquier número natural se puede representar como la suma de los valores de la función de Euler a partir de sus divisores naturales [12] :

\sum_{d\mid n}\varphi(d)=n.

La suma de todos los números menores que un número dado y primos relativos a él se expresa en términos de la función de Euler:

\sum_{1\leqslant k\leqslant n\atop(k,\;n)=1}k=\frac{1}{2}n\varphi(n), \; n > 1.

Muchos valores

El estudio de la estructura del conjunto de valores de la función de Euler es una tarea difícil por separado. Aquí se presentan sólo algunos de los resultados obtenidos en esta área [13] .

La función de Euler solo toma valores pares para Además, si tiene diferentes divisores primos impares, entonces $\varfi (n)$ $n > 2.$ $norte$ $r$ $2^{r} \mid \varphi(n).$

Demostración (la función de Euler solo toma valores pares para n > 2) De hecho, si es un número primo impar y entonces

pags

\alfa > 1

p^{\alfa - 1}(p - 1)

- incluso. De la igualdad

\varphi(n)=\prod_{i=1}^{k}p_i^{\alpha_i - 1}(p_i - 1)

sigue la afirmación.

En el análisis real, a menudo surge el problema de encontrar el valor de un argumento dado el valor de una función, o, en otras palabras, el problema de encontrar la función inversa . Un problema similar se puede plantear para la función de Euler. Sin embargo, se debe tener en cuenta lo siguiente.

Los valores de la función de Euler se repiten (por ejemplo, ), por lo que la función inversa es multivaluada . $\varphi(1) = \varphi(2) = 1$
La función de Euler sólo toma valores pares , es decir, si son impares y $norte > 2$ ${\ estilo de visualización \ varphi ^ {-1} (m) = \ var nada,}$ $metro$ ${\ estilo de visualización m \ neq 1.}$

En este sentido, se necesitan métodos especiales de análisis. Una herramienta útil para estudiar la preimagen es el siguiente teorema [14] . $\varphi$

Vamos - incluso, vamos a poner $metro$ $A(m)=m\prod _{p-1\mid m}{\frac {p}{p-1)),$ donde es sencillo. $pags$

si entonces

n \en \varphi^{-1}(m),

m<n\leqslant A(m).

Prueba del teorema Obviamente, si entonces Por otro lado, si y entonces

\varphi(n) = m,

metro < norte

\varfi(n) = m

n=p_{1}^{\alpha _{1}}\cdot \ldots \cdot p_{s}^{\alpha _{s)),

m = n \prod_{i=1}^s \frac{p_i-1}{p_i} \; \Flecha correcta\; n = m \prod_{i=1}^s \frac{p_i}{p_i-1}.

Sin embargo, si entonces por lo tanto

p\mid n,

p-1\mid\varphi (n).

\forall p_{i}:\;p_{i}-1\mid m.

Como consecuencia

n\leqslant A(m).

Este teorema muestra que la imagen inversa de un elemento es siempre un conjunto finito. También da la siguiente forma práctica de encontrar la preimagen: $m\en \mathbb {N}$

1) calcular ;

Soy)

2) calcular para todos a partir del medio intervalo ;

\varfi (n)

norte

{\ estilo de visualización (m, \, A (m)]}

3) todos los números para los que forman la imagen inversa del elemento .

norte,

\varphi(n)=m,

metro

Puede resultar que no exista tal número en el intervalo indicado que en este caso la preimagen sea el conjunto vacío . Vale la pena señalar que para el cálculo necesita conocer la descomposición en factores primos, lo que para los grandes es una tarea computacionalmente difícil . Luego, debe calcular la función de Euler una vez, lo que también requiere mucho tiempo para números grandes. Por lo tanto, encontrar la preimagen como un todo es un problema computacionalmente difícil. $norte,$ $\varphi(n)=m;$
$Soy)$ $metro$ $metro$ $A(m)-m$

Ejemplo 1 (cálculo de imagen previa)

Encontremos la preimagen de 4. Los divisores de 4 son los números 1, 2 y 4. Sumando uno a cada uno de ellos, obtenemos 2, 3, 5 - números primos. Calcular

A(4) = 4 \cdot \frac{2}{1} \cdot \frac{3}{2} \cdot \frac{5}{4} = 15.

Para encontrar la preimagen de 4, basta con considerar los números del 5 al 15. Habiendo hecho los cálculos, obtenemos:

\varphi ^{-1}(4)=\{5,\;8,\;10,\;12\}.

Ejemplo 2 (No todos los números pares son valores de la función de Euler)

No existe, por ejemplo, un número tal que sea: $metro,$ $\varfi(m) = 14.$

{\ estilo de visualización \ varphi ^ {-1} (14) = \ var nada.}

De hecho, los divisores de 14 son 1, 2, 7 y 14. Sumando uno cada uno, obtenemos 2, 3, 8, 15. De estos, solo los dos primeros números son primos. Es por eso

A(14) = 14 \cdot \frac{2}{1} \cdot \frac{3}{2} = 42.

Después de ordenar todos los números del 15 al 42, es fácil verificar que

\varphi (n)\neq 14,\;n\in (15,\,42).

Relaciones asintóticas

Las desigualdades más simples

El límite inferior para los valores de la función de Euler [15] [16] : ${\ estilo de visualización \ varphi (n) \ geqslant {\ sqrt {n}),}$

para todos excepto

norte,

n=2

n = 6.

Un límite superior para compuesto [15] [17] : $norte$ $\varphi (n)\leqslant n-{\sqrt {n)),$

para cualquier compuesto

norte.

Para todos los valores naturales , la doble desigualdad es válida [15] : $n\geqslant 3$ $\frac{\log2}{2} \cdot \frac{n}{\log{n}} < \varphi(n) < n.$

Comparación de φ( n ) con n

El límite superior de la relación se aproxima a la unidad con el crecimiento [18] : $\varphi(n)/n$ $norte$ $\varlimsup \frac{\varphi(n)}{n} = 1.$
Al mismo tiempo, la relación puede ser arbitrariamente grande [19] : $\varphi(n)/n^{1-\delta}$ $\forall \delta >0\colon {\frac {\varphi (n)}{n^{1-\delta ))}\rightarrow \infty .$

Relación de valores sucesivos

Las siguientes igualdades muestran cuán impredecible es la función de Euler [20] : $\lim \inf {\frac {\varphi (n+1)}{\varphi (n)))=0$ y $\lim \sup {\frac {\varphi (n+1)}{\varphi (n)))=\infty .$
Las fórmulas anteriores fueron obtenidas por Somayajulu en 1950. Y cuatro años más tarde, Schinzel y Sierpinski demostraron [20] que el conjunto

{\displaystyle \left\{{\frac {\varphi (n+1)}{\varphi (n)))),\;\;n=1,\;2,\;\ldots \right\))

denso en el conjunto de los números reales positivos.

En el mismo año establecieron [20] que el conjunto

{\displaystyle \left\{{\frac {\varphi (n)}{n)),\;\;n=1,\;2,\;\ldots \right\))

apretado en el intervalo

{\ estilo de visualización (0, \; 1).}

Asintóticas para sumas

La expresión exacta para la suma de valores sucesivos de la función de Euler [21] es: $\sum_{n\leqslant x}\varphi(n)=\frac{3}{\pi^2}x^2+O(x\ln x).$

Esto implica que el orden medio de la función de Euler es igual a . Este resultado es interesante porque permite obtener la probabilidad del evento de que dos números naturales elegidos al azar sean coprimos. Es decir, esta probabilidad es igual a [22] .

{\ estilo de visualización 6n/\ pi ^ {2}}

{\ estilo de visualización 6/\ pi ^ {2}}

Teniendo en cuenta la expresión anterior, podemos obtener las siguientes estimaciones asintóticas: $\sum _{k=1}^{n}{\frac {k}{\varphi (k)))=O(n)$ ; $\sum _{k=1}^{n}{\frac {1}{\varphi (k)))=O(\ln n)$ .
Usando la multiplicatividad de la función de Euler y las propiedades de la suma de divisores , es fácil establecer que [23] $\sigma(n)$ ${\frac {6}{\pi ^{2))}<{\frac {\varphi (n)\sigma (n)}{n^{2))}<1,\;n>1$ .

El orden de la función de Euler

En 1909, Landau obtuvo la igualdad [24] [25] : $\lim\inf\frac{\varphi(n)}{n}\log\log n = e^{-\gamma},$

donde es la constante de Euler-Mascheroni .

\gama

Este resultado se puede refinar. En 1962, se obtuvo una estimación más baja para la función de Euler [26] : $\varphi (n)\geqslant {\frac {n}{e^{\gamma}\log \log n+{\frac {2{,}5}{\log \log n))))$

para todos , con una excepción en este caso debe ser reemplazado por Este es uno de los límites inferiores más precisos para [27] .

n\geqslant 3

n=2\cdot 5\cdot 7\cdot 11\cdot 13\cdot 17\cdot 19\cdot 23;

{\ estilo de visualización 2{,} 5}

{\ estilo de visualización 2{,} 50637.}

\varfi (n)

Como estimación superior, se estableció el siguiente hecho [28] : existen infinitos números naturales tales que $norte$ $\varphi(n) < e^{-\gamma} \frac {n} {\log \log n}.$

Como comenta Paulo Ribenboim sobre la prueba de esta desigualdad [27] : "El método de prueba es interesante porque la desigualdad se establece primero bajo el supuesto de que la hipótesis de Riemann es verdadera, y luego bajo el supuesto de que no lo es". verdadero."

Relación con otras funciones

Función de Möbius

La siguiente fórmula se puede utilizar para calcular [29] : $\varfi (n)$ $\varphi(n)=\sum_{d\mid n} d\cdot\mu\left(\frac{n}{d}\right),$

donde es la función de Möbius .

\mamá)

Otras relaciones con la función de Möbius: $\sum_{k=1}^n\varphi(k)=\frac{1}{2}\left(1+\sum_{k=1}^n \mu(k)\left\lpiso\frac{n {k}\derecho\rpiso^2\derecho);$ $\sum_{k=1}^n\frac{\varphi(k)}{k}=\sum_{k=1}^n\frac{\mu(k)}{k}\left\lfloor\frac{ n}{k}\derecho\rpiso;$ $\sum _{d\mid n}{\frac {\mu ^{2}(d)}{\varphi (d)))={\frac {n}{\varphi (n)))$ [30] .

Serie de Dirichlet

La serie de Dirichlet con coeficientes se puede representar en términos de la función zeta de Riemann [31] : $\varfi (n)$ $\sum_{n=1}^\infty\frac{\varphi(n)}{n^s}=\frac{\zeta(s-1)}{\zeta(s)}, \; s > 2.$

Serie de Lambert

La suma de la serie de Lambert con coeficientes [32] : $\varfi (n)$ $\sum_{n=1}^\infty\frac{\varphi(n)q^n}{1-q^n}=\frac{q}{(1-q)^2}, \; |q|<1.$

Máximo común divisor

La función de Euler es la transformada discreta de Fourier del máximo común divisor [33] : $\varphi (n)=\sum \limits _{k=1}^{n}\gcd(k,\,n)e^{{-2\pi i}{\tfrac {k}{n }}}.$

Parte real:

\varphi (n)=\sum \limits _{k=1}^{n}\gcd(k,\,n)\cos {2\pi {\frac {k}{n))}.

A diferencia del producto de Euler, los cálculos que utilizan estas fórmulas no requieren conocimiento de divisores.

norte.

Conexión con cuadrados latinos

El número de cuadrados latinos cíclicos de orden con una primera fila fija viene dado por la función de Euler . Esta característica se puede usar al calcular el valor de la función de Euler contando el número correspondiente de cuadrados de un orden dado usando un algoritmo sin multiplicaciones y divisiones, sin embargo, esto es asintóticamente más lento que el cálculo basado en la factorización del argumento . Los cuadrados latinos diagonales cíclicos son un subconjunto de los cuadrados latinos diagonales cíclicos, por lo que el número de cuadrados latinos diagonales cíclicos con una primera fila fija (secuencia A123565 en OEIS ) es un límite inferior del valor de la función de Euler [34] . $norte$ ${\ estilo de visualización \ varphi (N)}$ $norte$ $norte$ ${\ estilo de visualización \ varphi (N)}$

Aplicaciones y ejemplos

Función de Euler en RSA

Basado en el algoritmo propuesto en 1978 por Ronald Rivest , Adi Shamir y Leonard Adleman , se construyó el primer sistema de cifrado de clave pública, llamado así por las primeras letras de los apellidos de los autores: el sistema RSA . La fuerza criptográfica de este sistema está determinada por la complejidad de la factorización de un número entero de bits. El papel clave en el algoritmo RSA lo desempeña la función de Euler, cuyas propiedades hacen posible construir un sistema criptográfico de clave pública [35] . $norte$

En la etapa de creación de un par de claves secretas y públicas,

\varphi(n) = \varphi(p \cdot q) = (p-1) \cdot (q-1),

donde y son simples. Luego se eligen números aleatorios de modo que $pags$ $q$ ${\ estilo de visualización d, \ e}$

d \cdot e = 1 \;\bmod \;\varphi(n).

A continuación, el mensaje se cifra con la clave pública del destinatario:

c = m^e\;\bmod\;n.

Después de eso, solo el propietario de la clave secreta puede descifrar el mensaje : $d$

m = c^d\;\bmod\;n.

La corrección de la última declaración se basa en el teorema de Euler y el teorema chino del resto .

Prueba de descifrado

Debido a la elección de números en la etapa de creación de claves.

e \cdot d = 1 + a \cdot \varphi(n).

Si entonces, teniendo en cuenta el teorema de Euler, ${\ estilo de visualización (m, \, n) = 1,}$

c^d = m^{ed} = m^{1}m^{a\varphi(n)} = m \cdot 1^{a} = m \;\bmod \;n.

En el caso general, y puede tener divisores comunes, pero el descifrado sigue siendo correcto. Sea De acuerdo con el teorema chino del resto: $metro$ $norte$ $m = 0 \;\bmod \;p.$

m = c^d \;\bmod \;n \;\Leftrightarrow \;\begin{cases} m = c^d \;\bmod \;p, \\ m = c^d \;\bmod \;q . \end{casos}

Sustituyendo obtenemos la identidad $c = m^e,$

\begin{casos} m^{ed} = 0 = m \;\bmod \;p, \\ m^{ed} = m(m^{q-1})^{a(p-1)} = m \cdot 1^{a(p-1)} = m \;\bmod \;q. \end{casos}

Como consecuencia,

m^{ed} = m\;\bmod\;pq.

Cálculo del elemento inverso

La función de Euler se puede utilizar para calcular el inverso de un elemento módulo , a saber [36] : $norte$

a^{-1} \equiv a^{\varphi(n)-1} \pmod n,

{\ estilo de visualización (a, \, n) = 1.}

Esta fórmula se sigue del teorema de Euler :

1 = (a \cdot a^{-1}) \cdot a^{\varphi(n)} \;\bmod \;n = a \cdot (a^{-1} \cdot a^{\varphi( n)}) \;\bmod \;n = a \cdot a^{\varphi(n) - 1} \;\bmod \;n.

Ejemplo (cálculo del elemento inverso)

Encuentre , es decir, un número tal que $5^{-1} \;\bmod\;7$ $X$

5 \cdot x \equiv 1 \pmod 7.

Obviamente, y no tienen divisores comunes excepto uno, , mientras que el número es primo y $5$ $7$ $(5.7)=1$ $7$

\varfi(7)=7-1=6,

Por lo tanto, es conveniente utilizar la fórmula anterior:

5^{6-1} \;\bmod \;7 = 5^{5} \;\bmod \;7 = 25 \cdot 25 \cdot 5 \;\bmod \;7 = (-3) \cdot ( -3) \cdot 5 \;\bmod \;7 = 9 \cdot 5 \;\bmod \;7 = 2 \cdot 5 \;\bmod \;7 = 3.

Es fácil comprobar lo que realmente

5 \cdot 3 \equiv 1 \pmod 7.

Observación 1 (Estimación de la complejidad computacional)

En general, para calcular recíprocos , el algoritmo euclidiano es más rápido que usar el teorema de Euler [37] , ya que la complejidad de bits del cálculo por el algoritmo euclidiano es de orden , mientras que el cálculo por el teorema de Euler requiere un orden de operaciones de bits, donde Sin embargo , en el caso de que se conozca la factorización , la complejidad computacional se puede reducir utilizando algoritmos de exponenciación rápida : el algoritmo de Montgomery o el algoritmo de "cuadrar y multiplicar" [38] . $O(k^2),$ $O(k^3)$ $k = \lceil \log_2{n} \rceil.$ $\varphi(n)-1$

Observación 2 (Sin solución en el caso ( a , n ) ≠ 1)

Si entonces no existe el elemento inverso , es decir, la ecuación ${\ estilo de visualización (a, \, n) \ neq 1,}$ $a$

a \cdot x \equiv 1 \pmod n

no tiene solución en el conjunto de los números naturales [39] .
Prueba. De hecho, supongamos

{\ estilo de visualización (a, \, n) = d> 1,}

y la solución existe. Entonces por la definición del máximo común divisor

a=d\cdot a',\ n=d\cdot n',

{\ estilo de visualización (a', \, n') = 1;}

para que puedas escribir:

d \cdot a' \cdot x = d \cdot n' \cdot t + 1,

dónde

t\en \mathbb {N} _{0},x\en \mathbb {N} ;

o, reorganizando los términos,

a' \cdot x - n' \cdot t = \frac{1}{d}.

A la izquierda hay un número entero distinto de cero, lo que significa que a la derecha debe haber un número entero distinto de cero, por lo tanto, con la necesidad

re=1

lo que contradice la suposición.

Solución de comparación lineal

El método de cálculo del elemento inverso se puede utilizar para resolver la comparación

a \cdot x \equiv b \pmod n.

La solución viene dada por la fórmula [37] :

x \equiv b \cdot a^{\varphi(n)-1} \pmod n,

{\ estilo de visualización (a, \, n) = 1.}

Ejemplo (solución de comparación lineal)

Considere la comparación

7 \cdot x \equiv 3 \pmod 9.

¿Cómo se puede utilizar esta fórmula: $(7.9)=1,$

x = 3 \cdot 7^{\varphi(3^{2})-1} \;\bmod \;9 = 3 \cdot 7^{3 \cdot (3-1) - 1} \;\bmod \ ;9 = 3 \cdot 7^{5} \;\bmod \;9 = 3 \cdot 49 \cdot 49 \cdot 7 \;\bmod \;9 = 3 \cdot 4 \cdot 4 \cdot 7 \;\ bmod\;9 = 3.

Por sustitución, nos aseguramos de que

7 \cdot 3 \equiv 3 \pmod 9.

Observación (No unicidad de una solución o ausencia de una solución en el caso de ( a , n ) ≠ 1)

Si , la comparación tiene una solución no única o no tiene solución. Es fácil comprobar que la comparación ${\ estilo de visualización (a, \, n) \ neq 1}$

2 \cdot x \equiv 3 \pmod 4

no tiene solución en el conjunto de los números naturales. Al mismo tiempo, la comparación

4 \cdot x \equiv 6 \pmod {22}

tiene dos soluciones

x = 7, \; x=18.

Cálculo del resto de una división

La función de Euler te permite calcular el resto de la división de números grandes [40] .

Ejemplo 1 (Últimos tres dígitos en la representación decimal de un número)

Encuentra los últimos tres dígitos en la notación decimal de un número Notando que $2^{100}.$

\varphi(125) = \varphi(5^3) = 5^3 - 5^2 = 100,

obtenemos

2^{100} \;\bmod \;125 = 2^{125 - 25} \;\bmod \;125 = 2^{\varphi(125)} \;\bmod \;125 = 1 \;\bmod \;125.

Pasando ahora de módulo a módulo tenemos: $125$ $1000$

2^{100} \equiv 1 \pmod{125} \equiv 376 \pmod{1000}.

Por lo tanto, la representación decimal de un número termina en $2^{100}$ $376.$

Ejemplo 2 (resto de la división por 1001)

Encontremos el resto después de dividir por Es fácil ver que $729^{720}$ $1001.$

{\ estilo de visualización (729, \; 1001) = 1.}

Por lo tanto, usando la multiplicatividad de la función de Euler y la igualdad

\varphi(p) = p - 1,

para cualquier simple

pags,

obtenemos

\varphi(1001) = \varphi(7 \cdot 11 \cdot 13) = \varphi(7) \cdot \varphi(11) \cdot \varphi(13) = 6 \cdot 10 \cdot 12 = 720.

Según el teorema de Euler

729^{720} \equiv 1 \pmod{1001}.

Encontrar el orden del grupo multiplicativo de un anillo de residuos

El grupo multiplicativo del módulo del anillo de residuos consta de clases de residuos [41] . Ejemplo. El sistema reducido de residuos módulo 14 consta de clases de residuos: $metro$ $\varfi(m)$
$\varfi(14) = 6$ $[1]_{14},\ [3]_{14},\ [5]_{14},\ [9]_{14},\ [11]_{14},\ [13 ]_{catorce}.$

Aplicaciones en teoría de grupos

El número de elementos generadores en un grupo cíclico finito es . En particular, si el grupo multiplicativo del anillo de residuos módulo es un grupo cíclico—lo cual es posible solo para , donde es un primo impar, es un número natural [42] —entonces hay generadores del grupo ( raíces primitivas módulo ) . Ejemplo. El grupo considerado en el ejemplo anterior tiene un generador: y $GRAMO$ $\varfi(|G|)$ $metro$ ${\displaystyle m=2,\;4,\;p^{n},\;2p^{n))$ $pags$ $norte$ $\varphi(\varphi(m))$ $metro$
${\ estilo de visualización \ mathbb {Z} _ {14} ^ {\ veces},}$ $\varphi(\varphi(14)) = \varphi(6) = 2$ $3$ $5.$

Cuestiones pendientes

El problema de Lemaire

Como saben, si es primo, entonces En 1932, Derrick Lemaire se preguntó si existe un número compuesto que sea divisor de . Lehmer consideró la ecuación: $pags$ $\varphi(p) = p - 1.$ $norte$ $\varfi (n)$ $n-1$

k\varfi(n) = n-1,

donde es un entero. Logró demostrar que si es una solución a una ecuación, entonces es primo o es un producto de siete o más números primos diferentes [43] . Más tarde se probaron otras afirmaciones fuertes. Entonces, en 1980, Cohen y Hagis demostraron que si se compone y se divide , entonces , ¿ dónde está el número de divisores primos? En 1970, Lieuwens estableció que si entonces y Wall en 1980 probó que si entonces [44] . $k$ $norte$ $norte$ $norte$ $\varfi (n)$ $n-1,$ $norte > 10^{20}$ ${\ estilo de visualización \ omega (n) \ geqslant 14,}$ $\ omega (n)$ $3\mid n,$ ${\ estilo de visualización \ omega (n) \ geqslant 213}$ $n>5{,}5\cdot 10^{570}.$ $30 \ medio n,$ ${\ estilo de visualización \ omega (n) \ geqslant 26}$

Hasta el día de hoy, no se sabe si existen soluciones compuestas para el problema de Lehmer. Si suponemos que no existen, entonces se obtiene el siguiente criterio de simplicidad: - prima si y sólo si [43] . $norte$ ${\ estilo de visualización \ varphi (n) \ mid n-1}$

Hipótesis de Carmichael

Incluso si miras los primeros diez valores de la función de Euler {1, 1, 2, 2, 4, 2, 6, 4, 6, 4}, llama la atención que hay muchas repeticiones entre ellos. La conjetura de Carmichael es que no existe tal valor que la función de Euler tomaría solo una vez. $metro$

En 1907, Carmichael propuso como ejercicio probar el siguiente enunciado [45] :

Si es un número natural, entonces existe un número natural tal que

norte

{\ estilo de visualización m \ neq n}

\varphi(n)=\varphi(m).

De lo contrario, esta afirmación se puede formular de la siguiente manera [46] : no existe un número natural tal que $metro$ $\dim(\varphi^{-1}(m)) = 1.$

Sin embargo, en 1922, Carmichael descubrió que su prueba contenía un error. En el mismo año, demostró que si luego esta estimación se mejoró repetidamente, y el valor moderno del límite inferior, a partir del cual vale la pena comenzar a buscar un contraejemplo para la conjetura de Carmichael, es Este valor fue obtenido por Schlafly y Wagon en 1994 usando el método de Klee [45] . $\dim(\varphi^{-1}(m)) = 1,$ ${\ estilo de visualización m> 10 ^ {37}.}$ $m=10^{10^{7}}.$

Vale la pena señalar que en 1999 Ford demostró el siguiente teorema [47] :

\forall k\geqslant 2\;\exists m\colon \dim(\varphi ^{-1}(m))=k.

Esto significa que, dado un número determinado , se puede encontrar entre el conjunto de valores de la función de Euler tal valor que se toma exactamente una vez. Sin embargo, nadie ha podido demostrar que no existe tal valor que la función de Euler tomaría una sola vez [46] . $k\geqslant 2,$ $metro,$ $k$

Véase también

Lista de objetos que llevan el nombre de Leonhard Euler

Notas

↑ Función de Euler // Enciclopedia matemática (en 5 volúmenes). - M .: Enciclopedia soviética , 1985. - T. 5. - S. 934.
↑ Sandifer, 2007 , pág. 203.
↑ Gabidulina, 2011 , RSA Systems.
↑ Secuencia OEIS A000010 _
↑ Burton, 2007 , Teorema 7.2, p. 133.
↑ Hardy, 1975 , Teorema 59, p. 52.
↑ Hardy, 1975 , Teorema 60, p. 53.
↑ 1 2 3 Sagalovich, 2007 , Cálculo de la función de Euler, p. 35-36.
↑ Burton, 2007 , Función Phi de Euler, p. 136.
↑ Weisstein, MathWorld, Función Totient
↑ Ruiz, S., Una congruencia con la función Euler Totient, 2004
↑ Vinogradov, 1952 , Función de Euler.
↑ La información de esta sección se basa en el artículo: Coleman, Some comments on Euler's totient function
↑ Gupta H., 1981
↑ 1 2 3 Handbook, 2005 , Desigualdades elementales para φ.
↑ Kendall y Osborn 1965
↑ Sierpinski y Schinzel 1988
↑ Hardy, 1975 , Teorema 326, p. 267.
↑ Hardy, 1975 , Teorema 327, p. 267.
↑ 1 2 3 Ribenboim, 1996 , Valores de la función de Euler, p. 38.
↑ Hardy, 1975 , Teorema 330, p. 268.
↑ Hardy, 1975 , Teorema 332, p. 269.
↑ Hardy, 1975 , Teorema 329, p. 267.
↑ Manual, 2005 , Sobre la función n /φ( n ).
↑ Hardy, 1975 , Teorema 328, p. 267.
↑ Rosser, J. Barkley y Schoenfeld, Lowell. Fórmulas aproximadas para algunas funciones de números primos // Illinois J. Math. : diario. - 1962. - vol. 6 , núm. 1 . - Pág. 64-94 . (Teorema 15)
↑ 1 2 Ribenboim, 1996 , Distribución de valores de la función de Euler, p. 320.
↑ Nicolás, 1983
↑ Vinogradov, 1952 , pág. 29-31.
↑ Rosica Dineva, Euler Totient, Möbius y las funciones divisorias
↑ Hardy, 1975 , Teorema 288, p. 250.
↑ Hardy, 1975 , Teorema 309, p. 258.
↑ Schramm, 2008
↑ Vatutin E. I. Sobre la enumeración de cuadrados latinos cíclicos y el cálculo del valor de la función de Euler a partir de ellos // Tecnologías y sistemas informáticos de alto rendimiento. 2020. V. 4, No. 2. S. 40–48.
↑ Gabidulin, 2011 , Sistema de encriptación RSA, p. 96.
↑ Alferov, 2002 , pág. 462-463.
↑ 1 2 Schneier, 1995 , La función Euler Totient.
↑ Gabidulin, 2011 , Encontrar el módulo inverso multiplicativo, p. 233.
↑ Schneier, 1995 , Teoría de números.
↑ Sagalovich, 2007 , pág. 36.
↑ Sagalovich, 2007 , Sistema reducido de deducciones.
↑ Vinogradov, 1952 , pág. 106.
↑ 12 Lehmer , 1932
↑ Ribenboim, 1996 , pág. 36-37.
↑ 1 2 Ribenboim, 1996 , p. 39-40.
↑ 1 2 Coleman, Algunas observaciones sobre la función totient de Euler
↑ Vado, 1999

Literatura

Carlos Sandifer. Las primeras matemáticas de Leonhard Euler. - MAA, 2007. - Pág. 391. - ISBN 0-88385-559-3 .
Jozsef Sandor, Dragoslav S. Mitrinovic, Borislav Crstici. Función φ de Euler // Manual de teoría de números I. - Springer, 2005. - 622 p.
Vinogradov I.M. Fundamentos de la teoría de números. - 5ª ed. - M. - L .: Gostekhizdat, 1952. - 180 p. — 100.000 copias.
GH Hardy, EMWright. Introducción a la teoría de los números. - cuarta edición. - Oxford: Oxford University Press, 1975. - 421 p.
Alferov A. P., Zubov A. Yu., Kuzmin A. S., Cheremushkin A. V. Elementos de álgebra y teoría de números // Fundamentos de criptografía. — 2ª ed., corregida. y adicional - M. : Helios ARV, 2002. - 480 p. — ISBN 5-85438-025-0 .
Bruce Schneier. Criptografía aplicada: protocolos, algoritmos y código fuente en C. - Australia: John Wiley & Sons, 1995. - ISBN 0-471-12845-7 .
Sagalovich Yu. L. Introducción a los códigos algebraicos - M. : MIPT , 2007. - 262 p. — ISBN 978-5-7417-0191-1
Pablo Ribenboim. El nuevo libro de registros de números primos. - Nueva York: Springer, 1996. - ISBN 0-387-94457-5 .
Gabidulin E. M., Kshevetsky A. S., Kolybelnikov A. I. Seguridad de la información: un tutorial. - M. : MIPT, 2011. - 262 p. — ISBN 5-7417-0377-9 .
David M Burton. Teoría elemental de números. — Sexta Edición. - Universidad de New Hampshire: McGraw-Hill, 2007. - 512 p. - ISBN 978-0-07-305188-8 .
Grupos de Arnold V.I. Euler y aritmética de progresiones geométricas. - M. : MTSNMO, 2003. - 44 p. — ISBN 5-94057-141-7 .

Enlaces

Arnold V. I., Los grupos de Euler y la aritmética de las progresiones geométricas (2003)
Coleman R., Algunas observaciones sobre la función totient de Euler (2012)
Dineva R., Euler Totient, Möbius y las funciones divisorias (2005)
Ford K., El número de soluciones de φ(x) = m (1999)
József Sándor, Dragoslav S. Mitrinovic, Borislav Crstici, Manual de teoría de números I (2005)
Gupta H., la función totient de Euler y su inversa (1981)
Hardy, Wright Introducción a la teoría de los números (2008)
Lehmer DH, Sobre la función Totient de Euler (1932)
Ruiz S., Una congruencia con la función de Euler Totient (2004)
Schramm, Wolfgang, La transformada de Fourier de funciones del máximo común divisor (2008)
Weisstein, Eric W. "Función Totient". De MathWorld: un recurso web de Wolfram. http://mathworld.wolfram.com/TotientFunction.html

diccionarios y enciclopedias	Britannica (en línea)