Función totiente de Euler

Número de números enteros coprimos con y menores que 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 totiente de Euler cuenta los números enteros positivos hasta un número entero dado n que son primos entre sí con respecto a n . Se escribe utilizando la letra griega phi como o , y también puede llamarse función phi de Euler . En otras palabras, es el número de números 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 números enteros k de esta forma a veces se denominan totalativos de n . ${\displaystyle \varphi (n)}$ ${\displaystyle \phi (n)}$

Por ejemplo, los totalativos de n = 9 son los seis números 1, 2, 4, 5, 7 y 8. Todos ellos son primos entre sí respecto de 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 lo tanto, φ (9) = 6. Como otro ejemplo, φ (1) = 1 ya que para n = 1 el único entero en el rango de 1 a n es el propio 1, y mcd(1, 1) = 1 .

La función totient de Euler es una función multiplicativa , lo que significa que si dos números m y n son primos entre sí, 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 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 de Gauss de 1801 Disquisitiones Arithmeticae , ^{[12] [13]} aunque Gauss no usó paréntesis alrededor del argumento y escribió φA . Por lo tanto, a menudo se la llama 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 totient de Jordan es una generalización del de Euler.

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

Cálculo de la función totient de Euler

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

Fórmula del producto de Euler

Dice así

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

donde el producto es sobre los números primos distintos que dividen a n . (Para la notación, véase Función aritmética ).

Una formulación equivalente es donde es la factorización prima de (es decir, son números primos distintos). $${\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),}$$ ${\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 la demostración: Sean A , B , C los conjuntos de números enteros positivos que son coprimos con y menores que m , n , mn , respectivamente, de modo que | A | = φ ( m ) , etc. Entonces hay una biyección entre A × B y C por 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).}$

Demostración : Puesto 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 que 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} múltiplos no mayores que p ^k . Por lo tanto, los otros números p ^k − p ^{k − 1} son todos primos entre sí con respecto a p ^k .

Prueba de la fórmula del producto de Euler

El teorema fundamental de la aritmética establece que si n > 1 existe una única expresión donde p ₁ < p ₂ < ... < p _r son números primos y cada k _i ≥ 1 . (El caso n = 1 corresponde al producto vacío). Usando 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 en su lugar 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 factores primos distintos 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, quedando 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 de Fourier discreta 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, utilizando y : A diferencia del producto de Euler y la fórmula de la suma de divisores, esta no requiere conocer los factores de n . Sin embargo, implica el cálculo del máximo común divisor de n y de cada entero positivo menor que n , lo que basta para proporcionar la factorización de todos modos. ${\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}}}$$

Suma del divisor

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. (Ver Función aritmética para convenciones de notación).

Una prueba es notar que φ ( d ) es también 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 con d . Puesto 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 se deduce. ^[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}}.}$

Poniéndolos en términos mínimos:

${\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 positivasa/d⁠ ≤ 1 cuyos denominadores son los divisores d = 1, 2, 4, 5, 10, 20 . Las fracciones con 20 como denominador son aquellas con numeradores relativamente primos a 20, es decir ⁠1/20⁠ , ⁠3/20⁠ , ⁠7/20⁠ , ⁠9/20⁠ , ⁠11/20⁠ , ⁠13/20⁠ , ⁠17/20⁠ , ⁠19/20⁠ ; por definición, se trata de φ (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 a 20. Un argumento similar se aplica para 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 siguientes:

Gráfica 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 solo 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 n⁠ . ^[20]

Teorema de Euler

Esto establece que si a y n son primos entre sí , entonces

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

El caso especial donde n es primo se conoce como el 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 exponente de descifrado (privado), 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 se puede resolver 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 primos grandes (elegidos al azar) p y q . Solo 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)}$

  Compare 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 | φ ( n )

• Para cualquier a > 1 y n > 6 tal que 4 ∤ n existe un l ≥ 2 n tal que l | φ ( a ⁿ − 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 no publicada como resultado específico: ^[25] véase la introducción de este artículo en la que se afirma que «hace mucho tiempo que se conoce»), tiene consecuencias importantes. Por ejemplo, descarta la distribución uniforme de los valores de en las progresiones aritméticas módulo para cualquier entero . ${\displaystyle \varphi (n)}$ ${\displaystyle q}$ ${\displaystyle q>1}$

• Para cada entero positivo fijo , la relación se cumple para casi todos los , es decir, para todos los valores de excepto los como . ${\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 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 ) .

Índice 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 a infinito, ^[30] para todo δ > 0

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

Estas dos fórmulas se pueden demostrar usando poco más que las fórmulas para φ ( n ) y la función suma del divisor σ ( 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,}$

Es cierto para n > 1 , queda 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 ....

Para probar esto no es necesario aplicar 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 verdad. ^{[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 fue demostrada por Jean-Louis Nicolas . Ribenboim dice: "El método de prueba es interesante, ya que la desigualdad se demuestra 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 orden 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 (On Euler's function. 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 de los 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 entre sí es6/π2^​⁠ .

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 nontotiente es un número natural que no es un número totiente. Todo entero impar mayor que 1 es trivialmente un nontotiente. También hay infinitos nontotientes pares, ^[41] y, de hecho, todo entero positivo tiene un múltiplo que es un nontotiente par. ^[42]

El número de números totientes 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 totientes 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áximoincógnita/(logaritmo x ) ^k⁠ para cualquier k positivo. ^[44]

Se sabe que la multiplicidad de m excede a m ^δ infinitamente a menudo 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 previamente conjeturado por Wacław Sierpiński , ^[47] y había sido obtenido como consecuencia de la hipótesis H de Schinzel . ^[43] En efecto, 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 de pacientes perfectos

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 totiente a un número n , la aplicamos nuevamente al totiente 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 totiente perfecto.

Aplicaciones

Ciclotomía

En la última sección de las Disquisitiones ^{[49] [50]} Gauss demuestra ^[51] que un n -gono regular puede construirse con regla y compás si φ ( n ) es una potencia de 2. Si n es una potencia de un número primo impar la fórmula para el totiente dice que su totiente puede ser una potencia de dos solo 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 solo se conocen cinco: 3, 5, 17, 257 y 65537. Fermat y Gauss conocían estos. Nadie ha podido demostrar si hay más.

Por lo tanto, un n -gono 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 de este tipo 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

Para configurar un sistema RSA es necesario 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 en privado.

Un mensaje, representado por un 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 sin resolver

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, libre de cuadrados y divisible por al menos siete 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]}

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 ) . Véase el teorema de Ford anterior.

Como se afirma en el artículo principal, si hay un único contraejemplo a 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 verdadera 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 todos los n ≥ p ₁₂₀₅₆₉ # donde γ es la constante de Euler y p ₁₂₀₅₆₉ # es el producto de los primeros 120569 primos. ^[57]

Véase también

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

• 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 Totient (𝛷)

Notas

1. "Función totiente de Euler". Khan Academy . 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. Véase el teorema de Euler.
7. L. Euler "Theoremata arithmetica nova methodo demonstrata" (Un teorema aritmético demostrado por 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 en línea 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 que son menores que N y relativamente primos con N (... aequalis sit multitudini numerorum ipso N minorum, qui simul ad eum sint primi, ...), que es la función phi, φ(N).
8. Sandifer, pág. 203
9. Graham et al. pág. 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. En la literatura se encuentran tanto φ ( n ) como ϕ ( n ) . Se trata de dos formas de la letra griega minúscula phi .
12. Gauss, Disquisitiones Arithmeticae artículo 38
13. Cajori, Florian (1929). Una historia de las notaciones matemáticas, volumen II . Open Court Publishing Company. §409.
14. JJ Sylvester (1879) "Sobre ciertas ecuaciones ternarias de forma cúbica", American Journal of Mathematics , 2  : 357-393; Sylvester acuña el término "totient" en la página 361.
15. "totient". Diccionario Oxford de inglés (2.ª ed.). Oxford University Press . 1989.
16. Schramm (2008)
17. Gauss, DA, artículo 39
18. Gauss, arte DA. 39, arts. 52-54
19. Graham y otros, págs. 134-135
20. Hardy y Wright 1979, tm. 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". Rocky Mountain J. Math . 15 (2): 579–588. doi : 10.1216/RMJ-1985-15-2-579 .
25. Pollack, P. (2023), "Dos problemas en 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, tm. 288
27. Hardy y Wright 1979, tm. 309
28. Hardy y Wright 1979, introducción al § 18.4
29. Hardy y Wright 1979, tomo 326
30. Hardy y Wright 1979, tomo 327
31. De hecho, el teorema de Chebyshev (Hardy y Wright 1979, thm.7) y el tercer teorema de Mertens son todo lo que se necesita.
32. Hardy y Wright 1979, tomo 436
33. Teorema 15 de Rosser, J. Barkley; Schoenfeld, Lowell (1962). "Fórmulas aproximadas para algunas funciones de números primos". Illinois J. Math . 6 (1): 64–94. doi : 10.1215/ijm/1255631807 .
34. Bach y Shallit, tm. 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, tomo 332
38. Ribenboim, pág. 38
39. Sándor, Mitrinović y Crstici (2006) p.16
40. Guy (2004) pág. 144
41. Sándor y Crstici (2004) p.230
42. Zhang, Mingzhi (1993). "Sobre los no-concientes". Revista de teoría de números . 43 (2): 168–172. doi : 10.1006/jnth.1993.1014 . ISSN  0022-314X. Zbl  0772.11001.
43. Ford, Kevin (1998). "La distribución de los tocientes". 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 y otros (2006) pág. 22
45. Sándor y otros (2006) pág. 21
46. Guy (2004) pág. 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 -gono. En 1837, Pierre Wantzel demostró lo contrario: si el n -gono es construible, entonces n debe satisfacer las condiciones de Gauss .
51. Gauss, DA, artículo 366
52. Gauss, DA, art. 366. Esta lista es la última frase de las Disquisitiones.
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. Guy (2004) pág. 142
57. Broughan, Kevin (2017). Equivalentes de la hipótesis de Riemann, volumen uno: Equivalentes aritméticos (primera edición). Cambridge University Press. 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 trabajos de Gauss sobre teoría de números: todas las pruebas de reciprocidad cuadrática, la determinación del signo de la suma de Gauss, las investigaciones sobre 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) , MIT Press Series in the Foundations of Computing, Cambridge, MA: The MIT Press , ISBN 0-262-02405-5, Zbl0873.11070 ​
• Dickson, Leonard Eugene, "Historia de la teoría de los números", vol. 1, capítulo 5 "Función de Euler, generalizaciones; serie de Farey", Chelsea Publishing 1952
• Ford, Kevin (1999), "El número de soluciones de φ( x ) =  m ", Anales de Matemáticas , 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 978-0-852-3-3 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, Zbl0836.00001 ​
• Guy, Richard K. (2004), Problemas sin resolver en teoría de números , Libros de problemas de matemáticas (3.ª ed.), Nueva York, NY: Springer-Verlag , ISBN 0-387-20860-7, Zbl1058.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. Edinburgh Sect. 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, Zbl0856.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, Zbl1151.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", Revista electrónica de teoría de números combinatorios , A50 (8(1)).

Enlaces externos

• "Función Totient", 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 multiplicativa Archivado el 28 de febrero de 2021 en Wayback Machine
• Calculadora de funciones totient de Euler en JavaScript: hasta 20 dígitos
• Dineva, Rosica, la función de Euler, la función de Möbius y la función divisora ​​Archivado el 16 de enero de 2021 en Wayback Machine.
• Plytage, Loomis, Polhill Resumen de la función phi de Euler