Función totient de Euler

Da el número de enteros primos relativamente a su entrada

"φ (n)" vuelve a dirigir aquí. Para otros usos, consulte Phi .

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 recuento de los números enteros positivos de hasta un determinado número entero n que son primos entre sí a n . Está escrito usando la letra griega phi como o , y también puede llamarse función phi de Euler . En otras palabras, es el número de enteros k en el rango 1 ≤ k ≤ n para el cual el máximo común divisor mcd ( n , k ) es igual a 1. ^{[2] [3]} Los enteros k${\displaystyle \varphi (n)}$${\displaystyle \phi (n)}$ de esta forma a veces se denominan derivados de n .

Por ejemplo, los totales de n = 9 son los seis números 1, 2, 4, 5, 7 y 8. Todos son primos relativos a 9, pero los otros tres números en este rango, 3, 6 y 9 no 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 número entero en el rango de 1 an es 1 en sí mismo, y mcd (1, 1) = 1 .

Función totient de Euler es una función multiplicativa , lo que significa que si dos números m y n son relativamente primo, 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 denotarlo. 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". ^[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 1801Disquisitiones Arithmeticae , ^{[12] [13]} aunque Gauss no usó paréntesis alrededor del argumento y escribió φA . Por lo tanto, a menudo se le 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 cototiente de n se define como n - φ ( n ) . Cuenta el número de enteros positivos menores o iguales an que tienen al menos un factor primo en común con n .

Calcular la función totient de Euler

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

Fórmula de producto de Euler

Afirma

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

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

Una formulación equivalente para , donde están los primos distintos que dividen n , es:${\displaystyle n=p_{1}^{k_{1}}p_{2}^{k_{2}}\cdots p_{r}^{k_{r}}}$${\displaystyle p_{1},p_{2},\ldots ,p_{r}}$

$${\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).}$$

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 enteros positivos que son coprimos ay 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 primaria

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} múltiplos menores que p ^k . Por lo tanto, los otrosnúmeros p ^k - p ^{k - 1} son todos relativamente primos 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). El uso repetido de la propiedad multiplicativa de φ y la fórmula para φ ( p ^k ) da${\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}-1}(p_{1}-1)\,p_{2}^{k_{2}-1}(p_{2}-1)\cdots p_{r}^{k_{r}-1}(p_{r}-1)\\[.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 da 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, dejando diez; una quinta parte de ellos es divisible entre 5, dejando ocho números coprimidos a 20; estos son: 1, 3, 7, 9, 11, 13, 17, 19.

La fórmula alternativa usa solo 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 totient 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 } . Luego

${\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}}}$$

A diferencia del producto de Euler y la fórmula de la suma del divisor, esta no requiere conocer los factores de n . Sin embargo, implica el cálculo del máximo común divisor de ny todo entero positivo menor que n , lo que de todos modos es suficiente para proporcionar la factorización.

Suma del divisor

La propiedad establecida por Gauss, ^[17] que

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

donde la suma está sobre todos los divisores positivos d de n , se puede probar de varias formas. (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 primos entre sí a d . Dado que cada elemento de C _n genera un subgrupo cíclico , y todos los subgrupos C _d ⊆ C _n son generados precisamente por φ ( d )elementos de C _n , la fórmula sigue. ^{[18] De manera} equivalente, la fórmula puede derivarse mediante el mismo argumento aplicado al grupo multiplicativo de las raíces n - ésimas de la unidad y las raíces d- ésimas primitivas 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}}.}$

Ponlos 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 las positivas k / d ≤ 1 cuyos denominadores son los divisores d = 1, 2, 4, 5, 10, 20 . Las fracciones con 20 como el denominador son aquellos 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 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 dividiendo 20. Un argumento similar 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 ≥ 1 . Esta fórmula también puede derivarse 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 el OEIS ) se muestran en la tabla y el gráfico siguientes:

Gráfico de los primeros 100 valores

φ ( n ) para 1 ≤ n ≤ 100

+	1	2	3	4	5	6	7	8	9	10
0	1	1	2	2	4	2	6	4	6	4
10	10	4	12	6	8	8	dieciséis	6	18	8
20	12	10	22	8	20	12	18	12	28	8
30	30	dieciséis	20	dieciséis	24	12	36	18	24	dieciséis
40	40	12	42	20	24	22	46	dieciséis	42	20
50	32	24	52	18	40	24	36	28	58	dieciséis
60	60	30	36	32	48	20	66	32	44	24
70	70	24	72	36	40	36	60	24	78	32
80	54	40	82	24	64	42	56	40	88	24
90	72	44	60	46	72	32	96	42	60	40

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 obtiene si y solo si n es un número primo. Un límite inferior simple es , que es bastante flexible: de hecho, el límite inferior del gráfico es proporcional an / log log n . ^[20]${\displaystyle \varphi (n)\geq {\sqrt {n/2}}}$

Teorema de euler

Artículo principal: 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 donde n es primo se conoce como el pequeño teorema de Fermat .

Esto se sigue 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 nPor lo 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 números primos grandes p y q (elegidos al azar) . 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 n\mid \varphi (a^{n}-1)\quad {\text{for }}a,n>1}$
• ${\displaystyle \varphi (mn)=\varphi (m)\varphi (n)\cdot {\frac {d}{\varphi (d)}}\quad {\text{where }}d=\operatorname {gcd} (m,n)}$

  Tenga en cuenta los casos especiales

  • ${\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

  • ${\displaystyle \operatorname {lcm} (m,n)\cdot \operatorname {gcd} (m,n)=m\cdot n}$
  (Ver mínimo común múltiplo ).
• φ ( 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 | φ ( una ⁿ - 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 n ).

• ${\displaystyle \sum _{d\mid n}{\frac {\mu ^{2}(d)}{\varphi (d)}}={\frac {n}{\varphi (n)}}}$ ^[21]
• ${\displaystyle \sum _{1\leq k\leq n \atop (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}{\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 ).

• ${\displaystyle \sum _{\stackrel {1\leq k\leq n}{\operatorname {gcd} (k,m)=1}}\!\!\!\!1=n{\frac {\varphi (m)}{m}}+O\left(2^{\omega (m)}\right)}$

  donde m > 1 es un número entero positivo y ω ( m ) es el número de factores primos distintos de m . ^[25]

Identidad de Menon

Artículo principal: 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 ) = σ 0 ( n ) es el número de divisores de n .

Fórmulas que involucran la proporción áurea

Schneider ^[26] encontró un par de identidades que conectan la función totient, la proporción áurea y la función de Möbius μ ( n ) . En esta sección φ ( n ) es la función totient, y φ = 1 + √ 5 / 2 = 1,618 ... es la proporción áurea.

Son:

${\displaystyle \phi =-\sum _{k=1}^{\infty }{\frac {\varphi (k)}{k}}\log \left(1-{\frac {1}{\phi ^{k}}}\right)}$

y

${\displaystyle {\frac {1}{\phi }}=-\sum _{k=1}^{\infty }{\frac {\mu (k)}{k}}\log \left(1-{\frac {1}{\phi ^{k}}}\right).}$

Restarlos da

${\displaystyle \sum _{k=1}^{\infty }{\frac {\mu (k)-\varphi (k)}{k}}\log \left(1-{\frac {1}{\phi ^{k}}}\right)=1.}$

Al aplicar la función exponencial a ambos lados de la identidad anterior se obtiene una fórmula de producto infinito para e :

${\displaystyle e=\prod _{k=1}^{\infty }\left(1-{\frac {1}{\phi ^{k}}}\right)\!\!^{\frac {\mu (k)-\varphi (k)}{k}}.}$

La prueba se basa en las dos fórmulas.

${\displaystyle {\begin{aligned}\sum _{k=1}^{\infty }{\frac {\varphi (k)}{k}}\left(-\log \left(1-x^{k}\right)\right)&={\frac {x}{1-x}}\\{\text{and}}\;\sum _{k=1}^{\infty }{\frac {\mu (k)}{k}}\left(-\log \left(1-x^{k}\right)\right)&=x,\qquad \quad {\text{for }}0<x<1.\end{aligned}}}$

Funciones generadoras

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

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

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

${\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 & Wright, el orden de φ ( n ) es "siempre 'casi n '". ^[29]

Primero ^[30]

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

pero a medida que n llega al infinito, ^[31] 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 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,}$

verdadero para n > 1 , se demuestra.

También tenemos ^[20]

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

Aquí γ es la constante de Euler , γ = 0,577215665 ... , por lo que e ^γ = 1,7810724 ... y E ^{- γ} = 0,56145948 ... .

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

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

De hecho, más es verdad. ^{[34] [35] [36]}

${\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 mostró Jean-Louis Nicolas . Ribenboim dice: "El método de prueba es interesante, ya que la desigualdad se muestra primero bajo el supuesto de que la hipótesis de Riemann es verdadera, en segundo lugar bajo el supuesto contrario". ^[36]

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

${\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 (esta es actualmente la estimación más conocida de este tipo). La "Gran O " representa una cantidad que está acotada 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 puede usarse para demostrar ^[38] que la probabilidad de que dos números elegidos al azar sean primos relativos es 6 / π ² .

Razón de valores consecutivos

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

${\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 ^{[39] [40]} 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 ^[39] que el conjunto

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

es denso en el intervalo (0,1).

Totient números

Un número totient es un valor de la función totient de Euler: es decir, una m para la cual hay al menos una n para la cual φ ( n ) = m . La valencia o multiplicidad de un número total m es el número de soluciones de esta ecuación. ^[41] Un no paciente es un número natural que no es un número total. Todo número entero impar que exceda de 1 es trivialmente un no sensible. También hay un número infinito de pares incluso no sensibles, ^[42] y, de hecho, todo entero positivo tiene un múltiplo que es un par no sensible. ^[43]

El número de números totales 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 ... . ^[44]

Si se cuenta de acuerdo con la multiplicidad, el número de números totales 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áximo x / (log x ) ^k para cualquier k positivo . ^[45]

Se sabe que la multiplicidad de m excede m ^δ infinitamente a menudo para cualquier δ <0.55655 . ^{[46] [47]}

Teorema de Ford

Ford (1999) demostró que para todo entero k ≥ 2 hay un número total 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 , ^[48] y se había obtenido como consecuencia de la hipótesis H de Schinzel . ^[44] De hecho, cada multiplicidad que se produce, lo hace infinitamente a menudo. ^{[44] [47]}

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

Números perfectos para los pacientes

Artículo principal: número perfecto de totient

Aplicaciones

Ciclotomía

Artículo principal: Polígono construible

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

Por lo tanto, un n -gon 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 ^[53]

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

El criptosistema RSA

Artículo principal: RSA (algoritmo)

Configuración de un sistema RSA consiste en elegir números primos grandes p y q , el cálculo de n = pq y k = φ ( n ) , y la búsqueda de dos números e y d tal que ed ≡ 1 (mod k ) . Los números n y e (la "clave de cifrado") se dan a conocer al público, 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 o si φ ( n ) pudiera calcularse sin factorizar n .

Problemas no resueltos

Conjetura de Lehmer

Artículo principal: el problema del totient de Lehmer

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

En 1933 demostró que si existe alguna 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 . ^[55] Además, Hagis mostró que si 3 divide n, entonces n > 10 ^1937042 y ω ( n ) ≥ 298848 . ^{[56] [57]}

Conjetura de Carmichael

Artículo principal: conjetura de la función totient de Carmichael

Esto establece que no hay un 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. ^[41]

Ver también

• Función de Carmichael
• Conjetura de Duffin-Schaeffer
• Generalizaciones del pequeño teorema de Fermat
• Número altamente compuesto
• Grupo multiplicativo de enteros módulo n
• Suma de Ramanujan
• Función sumatoria totiente
• Función psi de Dedekind

Notas

1. "Función totient de Euler" . Khan Academy . Consultado el 26 de febrero de 2016 .
2. Long (1972 , p. 85)
3. Pettofrezzo y Byrkit (1970 , p. 72)
4. Long (1972 , p. 162)
5. Pettofrezzo y Byrkit (1970 , p. 80)
6. Ver el teorema de Euler .
7. L. Euler " Theoremata arithmetica nova methodo demonstrata " (Un teorema aritmético probado 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 enteros que son más pequeños que N y relativamente primos de N (... aequalis sit multitudini numerorum ipso N minorum, qui simul ad eum sint primi, ...), que es el phi función, φ (N).
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, Florian (1929). Una historia de notaciones matemáticas Volumen II . Compañía Editorial Open Court. §409.
14. JJ Sylvester (1879) "En 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 de inglés de Oxford (2ª ed.). Prensa de la Universidad de Oxford . 1989.
16. Schramm (2008)
17. Gauss, DA, art 39
18. Gauss, DA art. 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). 16 . Berlín: VEB Deutscher Verlag der Wissenschaften . Zbl 0146.06003 . 
23. Lomadse, G., "El trabajo científico de Arnold Walfisz" (PDF) , Acta Arithmetica , 10 (3): 227-237
24. Sitaramachandrarao, R. (1985). "En un término de error de Landau II". Rocky Mountain J. Math . 15 : 579–588.
25. Bordellès en los enlaces externos
26. Todas las fórmulas de la sección son de Schneider (en los enlaces externos)
27. Hardy y Wright 1979 , thm. 288
28. Hardy y Wright 1979 , thm. 309
29. Hardy & Wright 1979 , introducción a § 18.4
30. Hardy y Wright 1979 , thm. 326
31. Hardy y Wright 1979 , thm. 327
32. De hecho,todo lo que se necesita esel teorema de Chebyshev ( Hardy & Wright 1979 , thm.7) y el tercer teorema de Mertens.
33. Hardy y Wright 1979 , thm. 436
34. 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.
35. Bach y Shallit, thm. 8.8.7
36. Ribenboim. El libro de los registros de números primos . Sección 4.IC^{[ se necesita cita completa ]}
37. Sándor, Mitrinović y Crstici (2006) págs. 24-25
38. Hardy y Wright 1979 , thm. 332
39. Ribenboim, p. 38
40. Sándor, Mitrinović y Crstici (2006) p.16
41. Guy (2004) p.144
42. Sándor y Crstici (2004) p.230
43. Zhang, Mingzhi (1993). "En no pacientes" . Revista de teoría de números . 43 (2): 168-172. doi : 10.1006 / jnth.1993.1014 . ISSN 0022-314X . Zbl 0772.11001 .  
44. Ford, Kevin (1998). "La distribución de los pacientes". Ramanujan J . 2 (1-2): 67-151. arXiv : 1104.3264 . doi : 10.1007 / 978-1-4757-4507-8_8 . ISSN 1382-4090 . Zbl 0914.11053 .  
45. Sándor et al (2006) p.22
46. Sándor et al (2006) p.21
47. Guy (2004) p.145
48. Sándor y Crstici (2004) p.229
49. Sándor y Crstici (2004) p.228
50. Gauss, DA. El 7º § son los arts. 336–366
51. Gauss demostró que si n satisface ciertas condiciones, entoncesse puede construirel n -gon. En 1837, Pierre Wantzel demostró lo contrario, si el n -gon es construible, entonces n debe satisfacer las condiciones de Gauss.
52. Gauss, DA, art 366
53. Gauss, DA, art. 366. Esta lista es la última oración del Disquisitiones
54. Ribenboim, págs. 36-37.
55. Cohen, Graeme L .; Hagis, Peter, Jr. (1980). "Sobre el número de factores primos de n si φ ( n ) divide n - 1 ". Nieuw Arch. Wiskd . Serie III. 28 : 177-185. ISSN 0028-9825 . Zbl 0436.10002 .  
56. Hagis, Peter, Jr. (1988). "En la ecuación M · φ ( n ) = n - 1 ". Nieuw Arch. Wiskd . Serie IV. 6 (3): 255–261. ISSN 0028-9825 . Zbl 0668.10006 .  
57. Guy (2004) p.142

Referencias

The Disquisitiones Arithmeticae se ha traducido 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 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 los Disquisitiones son de la forma Gauss, DA, art. nnn .

• Abramowitz, M .; Stegun, IA (1964), Manual de funciones matemáticas , Nueva York: Publicaciones de Dover , ISBN 0-486-61272-4. Ver párrafo 24.3.2.
• Bach, Eric ; Shallit, Jeffrey (1996), Teoría algorítmica de números (Vol I: Algoritmos eficientes) , Serie de prensa del MIT en los fundamentos de la computación, 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 ; Clarke, Arthur A. (traductor al inglés) (1986), Disquisitiones Arithmeticae (Segunda edición corregida) , Nueva York: Springer , ISBN 0-387-96254-9
• Gauss, Carl Friedrich ; Maser, H. (traductor al alemán) (1965), Untersuchungen uber hohere Arithmetik (Disquisitiones Arithmeticae y otros artículos sobre teoría de números) (segunda edición) , Nueva York: Chelsea, ISBN 0-8284-0191-8
• Graham, Ronald ; Knuth, Donald ; Patashnik, Oren (1994), Matemáticas concretas : una base para la informática (2a 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.a 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 los números (Quinta ed.), Oxford: Oxford University Press , ISBN 978-0-19-853171-5
• Long, Calvin T. (1972), Introducción elemental a la teoría de números (2a 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), The New Book of Prime Number Records (3.a ed.), Nueva York: Springer , ISBN 0-387-94457-5, Zbl  0856.11001
• Sandifer, Charles (2007), Las primeras matemáticas de Leonhard Euler , MAA, ISBN 0-88385-559-3
• 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 Totient" , Enciclopedia de Matemáticas , EMS Press , 2001 [1994]
• Función Phi de Euler y el teorema del residuo chino: prueba de que φ ( n ) es multiplicativo
• Calculadora de función totient de Euler en JavaScript: hasta 20 dígitos
• Funciones de Dineva, Rosica, Euler Totient, Möbius y Divisor
• Plytage, Loomis, Polhill resumiendo la función Euler Phi