Función totiente de Euler

Número de números enteros coprimos y no superiores a n

Los primeros mil valores de φ ( n ) . Los puntos en la línea superior representan φ ( p ) cuando p es un número primo, que es p − 1. ^[1]

En teoría de números , la función totient de Euler cuenta los números enteros positivos hasta un entero dado n que son primos relativos con n . Se escribe usando la letra griega phi como o , y también puede denominarse función phi de Euler . En otras palabras, es el número de enteros k en el rango 1 ≤ k ≤ n para los cuales el máximo común divisor mcd( n , k ) es igual a 1. ^{[2] [3]} Los enteros k de esta forma a veces son denominados totales de n . ${\displaystyle \varphi (n)}$ ${\displaystyle \phi (n)}$

Por ejemplo, los totales de n = 9 son los seis números 1, 2, 4, 5, 7 y 8. Todos son primos relativos con respecto a 9, pero los otros tres números en este rango, 3, 6 y 9, no lo son. , ya que mcd(9, 3) = mcd(9, 6) = 3 y mcd(9, 9) = 9 . Por tanto, φ (9) = 6 . Como otro ejemplo, φ (1) = 1 ya que para n = 1 el único número entero en el rango de 1 an es 1 mismo, y mcd(1, 1) = 1 .

La función totiente de Euler es una función multiplicativa , lo que significa que si dos números myn son primos relativos, entonces φ ( mn ) = φ ( m ) φ ( n ) . ^{[4] [5]} Esta función da el orden del grupo multiplicativo de números enteros módulo n (el grupo de unidades del anillo ). ^[6] También se utiliza para definir el sistema de cifrado RSA . ${\displaystyle \mathbb {Z} /n\mathbb {Z} }$

Historia, terminología y notación.

Leonhard Euler introdujo la función en 1763. ^{[7] [8] [9]} Sin embargo, en ese momento no eligió ningún símbolo específico para denotarla. En una publicación de 1784, Euler estudió la función más a fondo, eligiendo la letra griega π para denotarla: escribió πD para "la multitud de números menores que D , y que no tienen ningún divisor común con él". ^[10] Esta definición varía de la definición actual para la función totient en D = 1, pero por lo demás es la misma. La notación ahora estándar ^{[8] [11]} φ ( A ) proviene del tratado Disquisitiones Arithmeticae de Gauss de 1801 , ^{[12] [13]} aunque Gauss no usó paréntesis alrededor del argumento y escribió φA . Por lo tanto, a menudo se la denomina función phi de Euler o simplemente función phi .

En 1879, JJ Sylvester acuñó el término totient para esta función, ^{[14] [15]} por lo que también se la conoce como función totient de Euler , totient de Euler o totient de Euler . El paciente de Jordan es una generalización del de Euler.

El cotociente de n se define como n − φ ( n ) . Cuenta el número de enteros positivos menores o iguales que n que tienen al menos un factor primo en común con n .

Calcular la función totiente de Euler

Hay varias fórmulas para calcular φ ( n ) .

Fórmula del producto de Euler

Afirma

${\displaystyle \varphi (n)=n\prod _{p\mid n}\left(1-{\frac {1}{p}}\right),}$

donde el producto está entre los distintos números primos que dividen a n . (Para notación, consulte Función aritmética ).

Una formulación equivalente es

$${\displaystyle \varphi (n)=p_{1}^{k_{1}-1}(p_{1}{-}1)\,p_{2}^{k_{2}-1}(p_{2}{-}1)\cdots p_{r}^{k_{r}-1}(p_{r}{-}1),}$$

factorización prima ${\displaystyle n=p_{1}^{k_{1}}p_{2}^{k_{2}}\cdots p_{r}^{k_{r}}}$ ${\displaystyle n}$ ${\displaystyle p_{1},p_{2},\ldots ,p_{r}}$

La prueba de estas fórmulas depende de dos hechos importantes.

Phi es una función multiplicativa

Esto significa que si mcd( m , n ) = 1 , entonces φ ( m ) φ ( n ) = φ ( mn ) . Esquema de prueba: Sean A , B , C los conjuntos de números enteros positivos que son coprimos y menores que m , n , mn , respectivamente, de modo que | Un | = φ ( m ) , etc. Entonces hay una biyección entre A × B y C según el teorema del resto chino .

Valor de phi para un argumento de potencia prima

Si p es primo y k ≥ 1 , entonces

${\displaystyle \varphi \left(p^{k}\right)=p^{k}-p^{k-1}=p^{k-1}(p-1)=p^{k}\left(1-{\tfrac {1}{p}}\right).}$

Prueba : Dado que p es un número primo, los únicos valores posibles de mcd( p ^k , m ) son 1, p , p ² , ..., p ^k , y la única forma de tener mcd( p ^k , m ) > 1 es si m es un múltiplo de p , es decir, m ∈ { p , 2 p , 3 p , ..., p ^{k − 1} p = p ^k } , y hay p ^{k − 1} tales múltiplos no mayores que paquete .^​ Por lo tanto, los otros números p ^k − p ^{k − 1} son todos primos relativos de p ^k .

Prueba de la fórmula del producto de Euler

El teorema fundamental de la aritmética establece que si n > 1 hay una expresión única donde p ₁ < p ₂ < ... < p _r son números primos y cada k _i ≥ 1 . (El caso n = 1 corresponde al producto vacío). Al usar repetidamente la propiedad multiplicativa de φ y la fórmula para φ ( p ^k ) se obtiene ${\displaystyle n=p_{1}^{k_{1}}p_{2}^{k_{2}}\cdots p_{r}^{k_{r}},}$

${\displaystyle {\begin{array}{rcl}\varphi (n)&=&\varphi (p_{1}^{k_{1}})\,\varphi (p_{2}^{k_{2}})\cdots \varphi (p_{r}^{k_{r}})\\[.1em]&=&p_{1}^{k_{1}}\left(1-{\frac {1}{p_{1}}}\right)p_{2}^{k_{2}}\left(1-{\frac {1}{p_{2}}}\right)\cdots p_{r}^{k_{r}}\left(1-{\frac {1}{p_{r}}}\right)\\[.1em]&=&p_{1}^{k_{1}}p_{2}^{k_{2}}\cdots p_{r}^{k_{r}}\left(1-{\frac {1}{p_{1}}}\right)\left(1-{\frac {1}{p_{2}}}\right)\cdots \left(1-{\frac {1}{p_{r}}}\right)\\[.1em]&=&n\left(1-{\frac {1}{p_{1}}}\right)\left(1-{\frac {1}{p_{2}}}\right)\cdots \left(1-{\frac {1}{p_{r}}}\right).\end{array}}}$

Esto proporciona ambas versiones de la fórmula del producto de Euler.

Una prueba alternativa que no requiere la propiedad multiplicativa utiliza el principio de inclusión-exclusión aplicado al conjunto , excluyendo los conjuntos de números enteros divisibles por los divisores primos. ${\displaystyle \{1,2,\ldots ,n\}}$

Ejemplo

${\displaystyle \varphi (20)=\varphi (2^{2}5)=20\,(1-{\tfrac {1}{2}})\,(1-{\tfrac {1}{5}})=20\cdot {\tfrac {1}{2}}\cdot {\tfrac {4}{5}}=8.}$

En palabras: los distintos factores primos de 20 son 2 y 5; la mitad de los veinte números enteros del 1 al 20 son divisibles por 2, quedando diez; una quinta parte de ellos son divisibles por 5, lo que deja ocho números coprimos con 20; estos son: 1, 3, 7, 9, 11, 13, 17, 19.

La fórmula alternativa utiliza sólo números enteros:

$${\displaystyle \varphi (20)=\varphi (2^{2}5^{1})=2^{2-1}(2{-}1)\,5^{1-1}(5{-}1)=2\cdot 1\cdot 1\cdot 4=8.}$$

Transformada de Fourier

El totiente es la transformada discreta de Fourier del mcd , evaluada en 1. ^[16] Sea

${\displaystyle {\mathcal {F}}\{\mathbf {x} \}[m]=\sum \limits _{k=1}^{n}x_{k}\cdot e^{{-2\pi i}{\frac {mk}{n}}}}$

donde x _k = mcd( k , n ) para k ∈ {1, ..., n } . Entonces

${\displaystyle \varphi (n)={\mathcal {F}}\{\mathbf {x} \}[1]=\sum \limits _{k=1}^{n}\gcd(k,n)e^{-2\pi i{\frac {k}{n}}}.}$

La parte real de esta fórmula es

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

Por ejemplo, usando y : ${\displaystyle \cos {\tfrac {\pi }{5}}={\tfrac {{\sqrt {5}}+1}{4}}}$ ${\displaystyle \cos {\tfrac {2\pi }{5}}={\tfrac {{\sqrt {5}}-1}{4}}}$

$${\displaystyle {\begin{array}{rcl}\varphi (10)&=&\gcd(1,10)\cos {\tfrac {2\pi }{10}}+\gcd(2,10)\cos {\tfrac {4\pi }{10}}+\gcd(3,10)\cos {\tfrac {6\pi }{10}}+\cdots +\gcd(10,10)\cos {\tfrac {20\pi }{10}}\\&=&1\cdot ({\tfrac {{\sqrt {5}}+1}{4}})+2\cdot ({\tfrac {{\sqrt {5}}-1}{4}})+1\cdot (-{\tfrac {{\sqrt {5}}-1}{4}})+2\cdot (-{\tfrac {{\sqrt {5}}+1}{4}})+5\cdot (-1)\\&&+\ 2\cdot (-{\tfrac {{\sqrt {5}}+1}{4}})+1\cdot (-{\tfrac {{\sqrt {5}}-1}{4}})+2\cdot ({\tfrac {{\sqrt {5}}-1}{4}})+1\cdot ({\tfrac {{\sqrt {5}}+1}{4}})+10\cdot (1)\\&=&4.\end{array}}}$$

nnn

suma divisoria

La propiedad establecida por Gauss, ^[17] de que

${\displaystyle \sum _{d\mid n}\varphi (d)=n,}$

donde la suma es sobre todos los divisores positivos d de n , se puede demostrar de varias maneras. (Consulte Función aritmética para conocer las convenciones de notación).

Una prueba es observar que φ ( d ) también es igual al número de posibles generadores del grupo cíclico C _d  ; específicamente, si C _d = ⟨ g ⟩ con g ^d = 1 , entonces g ^k es un generador para cada k coprimo de d . Dado que cada elemento de C _n genera un subgrupo cíclico , y cada subgrupo C _d ⊆ C _n es generado precisamente por φ ( d ) elementos de C _n , la fórmula sigue. ^[18] De manera equivalente, la fórmula se puede derivar mediante el mismo argumento aplicado al grupo multiplicativo de las n -ésimas raíces de la unidad y las primitivas d -ésimas raíces de la unidad .

La fórmula también se puede derivar de la aritmética elemental. ^[19] Por ejemplo, sea n = 20 y considere las fracciones positivas hasta 1 con denominador 20:

${\displaystyle {\tfrac {1}{20}},\,{\tfrac {2}{20}},\,{\tfrac {3}{20}},\,{\tfrac {4}{20}},\,{\tfrac {5}{20}},\,{\tfrac {6}{20}},\,{\tfrac {7}{20}},\,{\tfrac {8}{20}},\,{\tfrac {9}{20}},\,{\tfrac {10}{20}},\,{\tfrac {11}{20}},\,{\tfrac {12}{20}},\,{\tfrac {13}{20}},\,{\tfrac {14}{20}},\,{\tfrac {15}{20}},\,{\tfrac {16}{20}},\,{\tfrac {17}{20}},\,{\tfrac {18}{20}},\,{\tfrac {19}{20}},\,{\tfrac {20}{20}}.}$

Póngalos en términos más bajos:

${\displaystyle {\tfrac {1}{20}},\,{\tfrac {1}{10}},\,{\tfrac {3}{20}},\,{\tfrac {1}{5}},\,{\tfrac {1}{4}},\,{\tfrac {3}{10}},\,{\tfrac {7}{20}},\,{\tfrac {2}{5}},\,{\tfrac {9}{20}},\,{\tfrac {1}{2}},\,{\tfrac {11}{20}},\,{\tfrac {3}{5}},\,{\tfrac {13}{20}},\,{\tfrac {7}{10}},\,{\tfrac {3}{4}},\,{\tfrac {4}{5}},\,{\tfrac {17}{20}},\,{\tfrac {9}{10}},\,{\tfrac {19}{20}},\,{\tfrac {1}{1}}}$

Estas veinte fracciones son todas positivas.k/d≤ 1 cuyos denominadores son los divisores d = 1, 2, 4, 5, 10, 20 . Las fracciones con 20 como denominador son aquellas que tienen numeradores relativamente primos con respecto a 20, es decir1/20,3/20,7/20,9/20,11/20,13/20,17/20,19/20; por definición, esto es φ (20) fracciones. De manera similar, hay φ (10) fracciones con denominador 10 y φ (5) fracciones con denominador 5, etc. Por lo tanto, el conjunto de veinte fracciones se divide en subconjuntos de tamaño φ ( d ) para cada d que divide 20. Un argumento similar se aplica a cualquier n.

La inversión de Möbius aplicada a la fórmula de la suma del divisor da

${\displaystyle \varphi (n)=\sum _{d\mid n}\mu \left(d\right)\cdot {\frac {n}{d}}=n\sum _{d\mid n}{\frac {\mu (d)}{d}},}$

donde μ es la función de Möbius , la función multiplicativa definida por y para cada primo p y k ≥ 2 . Esta fórmula también se puede derivar de la fórmula del producto multiplicando para obtener ${\displaystyle \mu (p)=-1}$ ${\displaystyle \mu (p^{k})=0}$ ${\textstyle \prod _{p\mid n}(1-{\frac {1}{p}})}$ ${\textstyle \sum _{d\mid n}{\frac {\mu (d)}{d}}.}$

Un ejemplo:

$${\displaystyle {\begin{aligned}\varphi (20)&=\mu (1)\cdot 20+\mu (2)\cdot 10+\mu (4)\cdot 5+\mu (5)\cdot 4+\mu (10)\cdot 2+\mu (20)\cdot 1\\[.5em]&=1\cdot 20-1\cdot 10+0\cdot 5-1\cdot 4+1\cdot 2+0\cdot 1=8.\end{aligned}}}$$

Algunos valores

Los primeros 100 valores (secuencia A000010 en la OEIS ) se muestran en la tabla y el gráfico a continuación:

Gráfico de los primeros 100 valores.

En el gráfico de la derecha, la línea superior y = n − 1 es un límite superior válido para todos los n distintos de uno, y se alcanza si y sólo si n es un número primo. Un límite inferior simple es , que es bastante impreciso: de hecho, el límite inferior del gráfico es proporcional a ${\displaystyle \varphi (n)\geq {\sqrt {n/2}}}$norte/registro registro sustantivo, masculino—. ^[20]

teorema de euler

Esto establece que si a y n son primos relativos , entonces

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

El caso especial en el que n es primo se conoce como pequeño teorema de Fermat .

Esto se desprende del teorema de Lagrange y del hecho de que φ ( n ) es el orden del grupo multiplicativo de números enteros módulo n .

El criptosistema RSA se basa en este teorema: implica que la inversa de la función a ↦ a ^e mod n , donde e es el exponente de cifrado (público), es la función b ↦ b ^d mod n , donde d , el (privado) ) exponente de descifrado, es el inverso multiplicativo de e módulo φ ( n ) . La dificultad de calcular φ ( n ) sin conocer la factorización de n es, por tanto, la dificultad de calcular d : esto se conoce como el problema RSA que puede resolverse factorizando n . El propietario de la clave privada conoce la factorización, ya que una clave privada RSA se construye eligiendo n como el producto de dos números primos grandes (elegidos al azar) p y q . Sólo n se divulga públicamente y, dada la dificultad de factorizar números grandes, tenemos la garantía de que nadie más conoce la factorización.

Otras fórmulas

• ${\displaystyle a\mid b\implies \varphi (a)\mid \varphi (b)}$
• ${\displaystyle m\mid \varphi (a^{m}-1)}$
• ${\displaystyle \varphi (mn)=\varphi (m)\varphi (n)\cdot {\frac {d}{\varphi (d)}}\quad {\text{where }}d=\operatorname {gcd} (m,n)}$

  En particular:

  • ${\displaystyle \varphi (2m)={\begin{cases}2\varphi (m)&{\text{ if }}m{\text{ is even}}\\\varphi (m)&{\text{ if }}m{\text{ is odd}}\end{cases}}}$
  • ${\displaystyle \varphi \left(n^{m}\right)=n^{m-1}\varphi (n)}$
• ${\displaystyle \varphi (\operatorname {lcm} (m,n))\cdot \varphi (\operatorname {gcd} (m,n))=\varphi (m)\cdot \varphi (n)}$

  Compara esto con la fórmula (ver mínimo común múltiplo ). ${\textstyle \operatorname {lcm} (m,n)\cdot \operatorname {gcd} (m,n)=m\cdot n}$

• φ ( n ) es par para n ≥ 3 .

  Además, si n tiene r factores primos impares distintos, 2 ^r | φ ( norte )

• Para cualquier a > 1 y n > 6 tal que 4 ∤ n existe un l ≥ 2 n tal que l | φ ( un ^norte − 1) .
• ${\displaystyle {\frac {\varphi (n)}{n}}={\frac {\varphi (\operatorname {rad} (n))}{\operatorname {rad} (n)}}}$

  donde rad( n ) es el radical de n (el producto de todos los primos distintos que dividen a n ).

• ${\displaystyle \sum _{d\mid n}{\frac {\mu ^{2}(d)}{\varphi (d)}}={\frac {n}{\varphi (n)}}}$ ^[21]
• ${\displaystyle \sum _{1\leq k\leq n-1 \atop gcd(k,n)=1}\!\!k={\tfrac {1}{2}}n\varphi (n)\quad {\text{for }}n>1}$
• ${\displaystyle \sum _{k=1}^{n}\varphi (k)={\tfrac {1}{2}}\left(1+\sum _{k=1}^{n}\mu (k)\left\lfloor {\frac {n}{k}}\right\rfloor ^{2}\right)={\frac {3}{\pi ^{2}}}n^{2}+O\left(n(\log n)^{\frac {2}{3}}(\log \log n)^{\frac {4}{3}}\right)}$ ( ^[22] citado en ^[23] )
• ${\displaystyle \sum _{k=1}^{n}\varphi (k)={\frac {3}{\pi ^{2}}}n^{2}+O\left(n(\log n)^{\frac {2}{3}}(\log \log n)^{\frac {1}{3}}\right)}$[Liu (2016)]
• ${\displaystyle \sum _{k=1}^{n}{\frac {\varphi (k)}{k}}=\sum _{k=1}^{n}{\frac {\mu (k)}{k}}\left\lfloor {\frac {n}{k}}\right\rfloor ={\frac {6}{\pi ^{2}}}n+O\left((\log n)^{\frac {2}{3}}(\log \log n)^{\frac {4}{3}}\right)}$ ^[22]
• ${\displaystyle \sum _{k=1}^{n}{\frac {k}{\varphi (k)}}={\frac {315\,\zeta (3)}{2\pi ^{4}}}n-{\frac {\log n}{2}}+O\left((\log n)^{\frac {2}{3}}\right)}$ ^[24]
• ${\displaystyle \sum _{k=1}^{n}{\frac {1}{\varphi (k)}}={\frac {315\,\zeta (3)}{2\pi ^{4}}}\left(\log n+\gamma -\sum _{p{\text{ prime}}}{\frac {\log p}{p^{2}-p+1}}\right)+O\left({\frac {(\log n)^{\frac {2}{3}}}{n}}\right)}$ ^[24]

  (donde γ es la constante de Euler-Mascheroni ).

La identidad de Menon.

En 1965, P. Kesava Menon demostró

${\displaystyle \sum _{\stackrel {1\leq k\leq n}{\gcd(k,n)=1}}\!\!\!\!\gcd(k-1,n)=\varphi (n)d(n),}$

donde d ( n ) = σ ₀ ( n ) es el número de divisores de n .

Divisibilidad por cualquier entero positivo fijo

La siguiente propiedad, que forma parte del «folclore» (es decir, aparentemente inédita como resultado específico: ^[25] véase la introducción de este artículo en la que se afirma que es «conocida desde hace mucho tiempo») tiene consecuencias importantes. Por ejemplo, descarta la distribución uniforme de los valores de en el módulo de progresiones aritméticas para cualquier número entero . ${\displaystyle \varphi (n)}$ ${\displaystyle q}$ ${\displaystyle q>1}$

• Para cada entero positivo fijo , la relación se cumple para casi todos , es decir, para todos menos los valores de as . ${\displaystyle q}$ ${\displaystyle q|\varphi (n)}$ ${\displaystyle n}$ ${\displaystyle o(x)}$ ${\displaystyle n\leq x}$ ${\displaystyle x\rightarrow \infty }$

Esta es una consecuencia elemental del hecho de que la suma de los recíprocos de los números primos congruentes con 1 módulo diverge, lo que a su vez es un corolario de la demostración del teorema de Dirichlet sobre progresiones aritméticas . ${\displaystyle q}$

Funciones generadoras

La serie de Dirichlet para φ ( n ) puede escribirse en términos de la función zeta de Riemann como: ^[26]

${\displaystyle \sum _{n=1}^{\infty }{\frac {\varphi (n)}{n^{s}}}={\frac {\zeta (s-1)}{\zeta (s)}}}$

donde el lado izquierdo converge para . ${\displaystyle \Re (s)>2}$

La función generadora de la serie de Lambert es ^[27]

${\displaystyle \sum _{n=1}^{\infty }{\frac {\varphi (n)q^{n}}{1-q^{n}}}={\frac {q}{(1-q)^{2}}}}$

que converge para | q | < 1 .

Ambos se prueban mediante manipulaciones de series elementales y las fórmulas para φ ( n ) .

Tasa de crecimiento

En palabras de Hardy y Wright, el orden de φ ( n ) es "siempre 'casi n '". ^[28]

Primero ^[29]

${\displaystyle \lim \sup {\frac {\varphi (n)}{n}}=1,}$

pero como n tiende al infinito, ^[30] para todo δ > 0

${\displaystyle {\frac {\varphi (n)}{n^{1-\delta }}}\rightarrow \infty .}$

Estas dos fórmulas se pueden probar usando poco más que las fórmulas para φ ( n ) y la función de suma divisoria σ ( n ) .

De hecho, durante la prueba de la segunda fórmula, la desigualdad

${\displaystyle {\frac {6}{\pi ^{2}}}<{\frac {\varphi (n)\sigma (n)}{n^{2}}}<1,}$

cierto para n > 1 , está demostrado.

También tenemos ^[20]

${\displaystyle \lim \inf {\frac {\varphi (n)}{n}}\log \log n=e^{-\gamma }.}$

Aquí γ es la constante de Euler , γ = 0,577215665... , entonces e ^γ = 1,7810724... y e ^{− γ} = 0,56145948 ....

Demostrar esto no requiere del todo el teorema de los números primos . ^{[31] [32]} Dado que log log n tiende al infinito, esta fórmula muestra que

${\displaystyle \lim \inf {\frac {\varphi (n)}{n}}=0.}$

De hecho, hay más cosas ciertas. ^{[33] [34] [35]}

${\displaystyle \varphi (n)>{\frac {n}{e^{\gamma }\;\log \log n+{\frac {3}{\log \log n}}}}\quad {\text{for }}n>2}$

y

${\displaystyle \varphi (n)<{\frac {n}{e^{\gamma }\log \log n}}\quad {\text{for infinitely many }}n.}$

La segunda desigualdad la demostró Jean-Louis Nicolas . Ribenboim dice: "El método de prueba es interesante porque la desigualdad se muestra primero bajo el supuesto de que la hipótesis de Riemann es verdadera y, en segundo lugar, bajo el supuesto contrario". ^{[35] : 173}

Para el pedido promedio, tenemos ^{[22] [36]}

${\displaystyle \varphi (1)+\varphi (2)+\cdots +\varphi (n)={\frac {3n^{2}}{\pi ^{2}}}+O\left(n(\log n)^{\frac {2}{3}}(\log \log n)^{\frac {4}{3}}\right)\quad {\text{as }}n\rightarrow \infty ,}$

debido a Arnold Walfisz , su prueba explota estimaciones sobre sumas exponenciales debidas a IM Vinogradov y NM Korobov . Mediante una combinación de los métodos de van der Corput y Vinogradov, H.-Q. Liu (Sobre la función de Euler. Proc. Roy. Soc. Edinburgh Sect. A 146 (2016), no. 4, 769–775) mejoró el término de error a

${\displaystyle O\left(n(\log n)^{\frac {2}{3}}(\log \log n)^{\frac {1}{3}}\right)}$

(esta es actualmente la estimación más conocida de este tipo). La " O grande " representa una cantidad que está limitada por una constante multiplicada por la función de n dentro del paréntesis (que es pequeña en comparación con n ² ).

Este resultado se puede utilizar para demostrar ^[37] que la probabilidad de que dos números elegidos al azar sean primos relativos es6/π ².

Relación de valores consecutivos

En 1950 Somayajulu demostró ^{[38] [39]}

${\displaystyle {\begin{aligned}\lim \inf {\frac {\varphi (n+1)}{\varphi (n)}}&=0\quad {\text{and}}\\[5px]\lim \sup {\frac {\varphi (n+1)}{\varphi (n)}}&=\infty .\end{aligned}}}$

En 1954 Schinzel y Sierpiński reforzaron esto, demostrando ^{[38] [39]} que el conjunto

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

es denso en los números reales positivos. También demostraron ^[38] que el conjunto

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

es denso en el intervalo (0,1).

Números de pacientes

Un número totiente es un valor de la función totiente de Euler: es decir, un m para el cual hay al menos un n para el cual φ ( n ) = m . La valencia o multiplicidad de un número totiente m es el número de soluciones de esta ecuación. ^[40] Un no paciente es un número natural que no es un número de paciente. Todo número impar superior a 1 es trivialmente un no paciente. También hay infinitos no-tocientes pares, ^[41] y de hecho cada número entero positivo tiene un múltiplo que es un no-tociente par. ^[42]

El número de números de pacientes hasta un límite dado x es

${\displaystyle {\frac {x}{\log x}}e^{{\big (}C+o(1){\big )}(\log \log \log x)^{2}}}$

para una constante C = 0,8178146... . ^[43]

Si se cuenta de acuerdo con la multiplicidad, el número de números tocientes hasta un límite dado x es

${\displaystyle {\Big \vert }\{n:\varphi (n)\leq x\}{\Big \vert }={\frac {\zeta (2)\zeta (3)}{\zeta (6)}}\cdot x+R(x)}$

donde el término de error R es de orden como máximoX/( logx ) ^kpara cualquier k positivo . ^[44]

Se sabe que la multiplicidad de m excede m ^δ infinitamente para cualquier δ < 0,55655 . ^{[45] [46]}

teorema de ford

Ford (1999) demostró que para cada entero k ≥ 2 existe un número totiente m de multiplicidad k : es decir, para el cual la ecuación φ ( n ) = m tiene exactamente k soluciones; este resultado había sido conjeturado previamente por Wacław Sierpiński , ^[47] y se había obtenido como consecuencia de la hipótesis H de Schinzel . ^[43] De hecho, cada multiplicidad que ocurre, lo hace infinitamente a menudo. ^{[43] [46]}

Sin embargo, no se conoce ningún número m con multiplicidad k = 1 . La conjetura de la función totiente de Carmichael es la afirmación de que no existe tal m . ^[48]

Números perfectos de pacientes

Un número totiente perfecto es un número entero que es igual a la suma de sus totientes iterados. Es decir, aplicamos la función totient a un número n , la aplicamos nuevamente al totient resultante, y así sucesivamente, hasta llegar al número 1, y sumamos la secuencia de números resultante; si la suma es igual a n , entonces n es un número perfecto.

Aplicaciones

ciclotomía

En la última sección de las Disquisitiones ^{[49] [50]} Gauss demuestra ^[51] que se puede construir un n -gón regular con regla y compás si φ ( n ) es una potencia de 2. Si n es una potencia de un número impar número primo la fórmula para el totiente dice que su totiente puede ser una potencia de dos sólo si n es una primera potencia y n − 1 es una potencia de 2. Los primos que son uno más que una potencia de 2 se llaman primos de Fermat , y sólo se conocen cinco: 3, 5, 17, 257 y 65537. Fermat y Gauss los conocían. Nadie ha podido demostrar si hay más.

Por lo tanto, un n -gón regular tiene una construcción de regla y compás si n es un producto de distintos primos de Fermat y cualquier potencia de 2. Los primeros n son ^[52]

2, 3, 4, 5, 6, 8, 10, 12, 15, 16, 17, 20, 24, 30, 32, 34, 40,... (secuencia A003401 en la OEIS ).

Teorema de los números primos para progresiones aritméticas

El criptosistema RSA

Configurar un sistema RSA implica elegir números primos grandes p y q , calcular n = pq y k = φ ( n ) y encontrar dos números e y d tales que ed ≡ 1 (mod k ) . Los números n y e (la "clave de cifrado") se hacen públicos y d (la "clave de descifrado") se mantiene privado.

Un mensaje, representado por un número entero m , donde 0 < m < n , se cifra calculando S = m ^e (mod n ) .

Se descifra calculando t = S ^d (mod n ) . El teorema de Euler se puede utilizar para demostrar que si 0 < t < n , entonces t = m .

La seguridad de un sistema RSA se vería comprometida si el número n pudiera factorizarse eficientemente o si φ ( n ) pudiera calcularse eficientemente sin factorizar n .

Problemas no resueltos

la conjetura de lehmer

Si p es primo, entonces φ ( p ) = p − 1 . En 1932, DH Lehmer preguntó si existen números compuestos n tales que φ ( n ) divida a n − 1 . No se conoce ninguno. ^[53]

En 1933 demostró que si existe tal n , debe ser impar, sin cuadrados y divisible por al menos siete números primos (es decir, ω ( n ) ≥ 7 ). En 1980 Cohen y Hagis demostraron que n > 10 ²⁰ y que ω ( n ) ≥ 14 . ^[54] Además, Hagis demostró que si 3 divide a n, entonces n > 10 ^1937042 y ω ( n ) ≥ 298848 . ^{[55] [56]}

La conjetura de Carmichael

Esto establece que no existe ningún número n con la propiedad de que para todos los demás números m , m ≠ n , φ ( m ) ≠ φ ( n ) . Vea el teorema de Ford arriba.

Como se indica en el artículo principal, si hay un solo contraejemplo para esta conjetura, debe haber infinitos contraejemplos, y el más pequeño tiene al menos diez mil millones de dígitos en base 10. ^[40]

hipótesis de riemann

La hipótesis de Riemann es cierta si y sólo si la desigualdad

${\displaystyle {\frac {n}{\varphi (n)}}<e^{\gamma }\log \log n+{\frac {e^{\gamma }(4+\gamma -\log 4\pi )}{\sqrt {\log n}}}}$

es cierto para todo n ≥ p ₁₂₀₅₆₉ # donde γ es la constante de Euler y p ₁₂₀₅₆₉ # es el producto de los primeros 120569 números primos. ^[57]

Ver también

• Función Carmichael (λ)
• Función psi de Dedekind (𝜓)
• Función divisora ​​(σ)

• Conjetura de Duffin-Schaeffer
• Generalizaciones del pequeño teorema de Fermat
• Número altamente compuesto

• Grupo multiplicativo de números enteros módulo n
• suma de ramanujan
• Función sumatoria de Totiente (𝛷)

Notas

1. "Función totiente de Euler". Academia Khan . Consultado el 26 de febrero de 2016 .
2. Largo (1972, pág.85)
3. Pettofrezzo y Byrkit (1970, pág.72)
4. Largo (1972, pág.162)
5. Pettofrezzo y Byrkit (1970, pág.80)
6. Ver el teorema de Euler.
7. L. Euler "Theoremata arithmetica nova Methodo demonstrata" (Un teorema aritmético demostrado mediante un nuevo método), Novi commentarii academiae scientiarum imperialis Petropolitanae (Nuevas memorias de la Academia Imperial de Ciencias de San Petersburgo), 8 (1763), 74-104 . (La obra fue presentada en la Academia de San Petersburgo el 15 de octubre de 1759. Una obra con el mismo título fue presentada en la Academia de Berlín el 8 de junio de 1758). Disponible on-line en: Ferdinand Rudio , ed. , Leonhardi Euleri Commentationes Arithmeticae , volumen 1, en: Leonhardi Euleri Opera Omnia , serie 1, volumen 2 (Leipzig, Alemania, BG Teubner, 1915), páginas 531–555. En la página 531, Euler define n como el número de números enteros menores que N y relativamente primos con N (... aequalis sit multitudini numerorum ipso N minorum, qui simul ad eum sint primi,...), que es el phi función, φ(norte).
8. Sandifer, pág. 203
9. Graham y col. pag. 133 nota 111
10. L. Euler, Speculationes circa quasdam insignes proprietates numerorum , Acta Academiae Scientarum Imperialis Petropolitinae, vol. 4, (1784), págs. 18–30, u Opera Omnia, Serie 1, volumen 4, págs. 105–115. (La obra fue presentada en la Academia de San Petersburgo el 9 de octubre de 1775).
11. Tanto φ ( n ) como ϕ ( n ) se ven en la literatura. Estas son dos formas de la letra griega minúscula phi .
12. Gauss, Disquisitiones Arithmeticae artículo 38
13. Cajori, Florián (1929). Una historia de las notaciones matemáticas Volumen II . Compañía editorial Open Court. §409.
14. JJ Sylvester (1879) "Sobre ciertas ecuaciones de forma cúbica ternaria", American Journal of Mathematics , 2  : 357-393; Sylvester acuña el término "totiente" en la página 361.
15. "tociente". Diccionario de inglés Oxford (2ª ed.). Prensa de la Universidad de Oxford . 1989.
16. Schramm (2008)
17. Gauss, DA, artículo 39
18. Gauss, arte DA. 39, arts. 52-54
19. Graham y col. págs. 134-135
20. Hardy y Wright 1979, thm. 328
21. Dineva (en referencias externas), prop. 1
22. Walfisz, Arnold (1963). Weylsche Exponentialsummen in der neueren Zahlentheorie . Mathematische Forschungsberichte (en alemán). vol. 16. Berlín: VEB Deutscher Verlag der Wissenschaften . Zbl  0146.06003.
23. Lomadse, G. (1964), "El trabajo científico de Arnold Walfisz" (PDF) , Acta Arithmetica , 10 (3): 227–237, doi :10.4064/aa-10-3-227-237
24. Sitaramachandrarao, R. (1985). "Sobre un término de error de Landau II". Montañas Rocosas J. Matemáticas . 15 (2): 579–588. doi : 10.1216/RMJ-1985-15-2-579 .
25. Pollack, P. (2023), "Dos problemas sobre la distribución de la función lambda de Carmichael", Mathematika , 69 : 1195–1220, arXiv : 2303.14043 , doi : 10.1112/mtk.12222
26. Hardy y Wright 1979, thm. 288
27. Hardy y Wright 1979, thm. 309
28. Hardy y Wright 1979, introducción al § 18.4
29. Hardy y Wright 1979, thm. 326
30. Hardy y Wright 1979, thm. 327
31. De hecho, todo lo que se necesita es el teorema de Chebyshev (Hardy y Wright 1979, thm.7) y el tercer teorema de Mertens.
32. Hardy y Wright 1979, thm. 436
33. Teorema 15 de Rosser, J. Barkley; Schoenfeld, Lowell (1962). "Fórmulas aproximadas para algunas funciones de números primos". Illinois J. Matemáticas . 6 (1): 64–94. doi : 10.1215/ijm/1255631807 .
34. Bach y Shallit, thm. 8.8.7
35. Ribenboim (1989). "¿Cómo se distribuyen los números primos? §IC La distribución de valores de la función de Euler". El libro de registros de números primos (2ª ed.). Nueva York: Springer-Verlag. págs. 172-175. doi :10.1007/978-1-4684-0507-1_5. ISBN 978-1-4684-0509-5.
36. Sándor, Mitrinović y Crstici (2006) págs. 24-25
37. Hardy y Wright 1979, thm. 332
38. Ribenboim, p.38
39. Sándor, Mitrinović y Crstici (2006) p.16
40. Guy (2004) p.144
41. Sándor y Crstici (2004) p.230
42. Zhang, Mingzhi (1993). "Sobre los no pacientes". Revista de teoría de números . 43 (2): 168-172. doi : 10.1006/junio.1993.1014 . ISSN  0022-314X. Zbl  0772.11001.
43. Ford, Kevin (1998). "La distribución de los pacientes". Ramanujan J. Desarrollos en Matemáticas. 2 (1–2): 67–151. arXiv : 1104.3264 . doi :10.1007/978-1-4757-4507-8_8. ISBN 978-1-4419-5058-1. ISSN  1382-4090. Zbl  0914.11053.
44. Sándor et al (2006) p.22
45. Sándor et al (2006) p.21
46. Guy (2004) p.145
47. Sándor y Crstici (2004) p.229
48. Sándor y Crstici (2004) p.228
49. Gauss, DA. El § 7º son los arts. 336–366
50. Gauss demostró que si n satisface ciertas condiciones, entonces se puede construir el n -gon. En 1837, Pierre Wantzel demostró lo contrario: si el n -gon es construible, entonces n debe satisfacer las condiciones de Gauss.
51. Gauss, DA, artículo 366
52. Gauss, DA, arte. 366. Esta lista es la última frase de las Disquisiciones
53. Ribenboim, págs. 36-37.
54. Cohen, Graeme L.; Hagis, Peter Jr. (1980). "Sobre el número de factores primos de n si φ ( n ) divide n − 1 ". Nuevo Arco. Wiskd . III Serie. 28 : 177–185. ISSN  0028-9825. Zbl  0436.10002.
55. Hagis, Peter Jr. (1988). "Sobre la ecuación M ·φ( n ) = n − 1 ". Nuevo Arco. Wiskd . Serie IV. 6 (3): 255–261. ISSN  0028-9825. Zbl  0668.10006.
56. Chico (2004) p.142
57. Broughan, Kevin (2017). Equivalentes de la hipótesis de Riemann, volumen uno: equivalentes aritméticos (Primera ed.). Prensa de la Universidad de Cambridge. ISBN 978-1-107-19704-6.Corolario 5.35

Referencias

Las Disquisitiones Arithmeticae han sido traducidas del latín al inglés y al alemán. La edición alemana incluye todos los artículos de Gauss sobre teoría de números: todas las pruebas de la reciprocidad cuadrática, la determinación del signo de la suma de Gauss, las investigaciones sobre la reciprocidad bicuadrática y notas inéditas.

Las referencias a las Disquisitiones son de la forma Gauss, DA, art. nnn .

• Abramowitz, M .; Stegun, IA (1964), Manual de funciones matemáticas, Nueva York: Dover Publications , ISBN 0-486-61272-4. Véase el párrafo 24.3.2.
• Bach, Eric ; Shallit, Jeffrey (1996), Teoría algorítmica de números (Vol I: Algoritmos eficientes) , Serie de MIT Press sobre los fundamentos de la informática, Cambridge, MA: The MIT Press , ISBN 0-262-02405-5, Zbl  0873.11070
• Dickson, Leonard Eugene, "Historia de la teoría de los números", vol 1, capítulo 5 "Función de Euler, generalizaciones; serie Farey", Chelsea Publishing 1952
• Ford, Kevin (1999), "El número de soluciones de φ( x ) =  m ", Annals of Mathematics , 150 (1): 283–311, doi :10.2307/121103, ISSN  0003-486X, JSTOR  121103, MR  1715326 , Zbl  0978.11053.
• Gauss, Carl Friedrich (1986), Disquisitiones Arithmeticae (Segunda edición corregida) , traducido por Clarke, Arthur A., ​​Nueva York: Springer , ISBN 0-387-96254-9
• Gauss, Carl Friedrich (1965), Untersuchungen uber hohere Arithmetik (Disquisitiones Arithmeticae y otros artículos sobre teoría de números) (Segunda edición) , traducido por Maser, H., Nueva York: Chelsea, ISBN 0-8284-0191-8
• Graham, Ronald ; Knuth, Donald ; Patashnik, Oren (1994), Matemáticas concretas : una base para la informática (2ª ed.), Reading, MA: Addison-Wesley, ISBN 0-201-55802-5, Zbl  0836.00001
• Guy, Richard K. (2004), Problemas no resueltos en teoría de números , Libros de problemas en matemáticas (3.ª ed.), Nueva York, NY: Springer-Verlag , ISBN 0-387-20860-7, Zbl  1058.11001
• Hardy, GH ; Wright, EM (1979), Introducción a la teoría de números (Quinta ed.), Oxford: Oxford University Press , ISBN 978-0-19-853171-5
• Liu, H.-Q. (2016), "Sobre la función de Euler", Proc. Roy. Soc. Secta de Edimburgo. A , 146 (4).
• Long, Calvin T. (1972), Introducción elemental a la teoría de números (2ª ed.), Lexington: DC Heath and Company , LCCN  77-171950
• Pettofrezzo, Anthony J.; Byrkit, Donald R. (1970), Elementos de la teoría de números , Englewood Cliffs: Prentice Hall , LCCN  77-81766
• Ribenboim, Paulo (1996), El nuevo libro de registros de números primos (3.ª ed.), Nueva York: Springer , ISBN 0-387-94457-5, Zbl  0856.11001
• Sandifer, Charles (2007), Las primeras matemáticas de Leonhard Euler , MAA, ISBN 978-0-88385-559-1
• Sándor, József; Mitrinović, Dragoslav S.; Crstici, Borislav, eds. (2006), Manual de teoría de números I , Dordrecht: Springer-Verlag , págs. 9–36, ISBN 1-4020-4215-9, Zbl  1151.11300
• Sándor, Jozsef; Crstici, Borislav (2004). Manual de teoría de números II . Dordrecht: Académico Kluwer. págs. 179–327. ISBN 1-4020-2546-7. Zbl  1079.11001.
• Schramm, Wolfgang (2008), "La transformada de Fourier de funciones del máximo común divisor", Electronic Journal of Combinatorial Number Theory , A50 (8(1)).

enlaces externos

• "Función del paciente", Enciclopedia de Matemáticas , EMS Press , 2001 [1994]
• La función Phi de Euler y el teorema del resto chino: prueba de que φ (n) es multiplicativo Archivado el 28 de febrero de 2021 en Wayback Machine.
• Calculadora de función totient de Euler en JavaScript: hasta 20 dígitos
• Dineva, Rosica, Euler Totient, Möbius y las funciones divisoras Archivado el 16 de enero de 2021 en Wayback Machine.
• Plytage, Loomis y Polhill resumen la función Euler Phi