Función φ de Euler

Los primeros mil valores de $\scriptstyle \varphi (n)$.​

La función φ de Euler (también llamada función indicatriz de Euler o función totiente) es una función importante en teoría de números. Si n es un número entero positivo, entonces φ(n) se define como la cantidad de enteros positivos menores a n y coprimos con n, es decir, formalmente se puede definir como:​​

$\varphi (n)=|\{m\in \mathbb {N} |m\leq n\land \mathrm {mcd} (m,n)=1\}|$

donde |·| significa la cardinalidad del conjunto descrito.

La función φ es importante principalmente porque proporciona el tamaño del grupo multiplicativo de enteros módulo n. Más precisamente, $\varphi (n)$ es el orden del grupo de unidades del anillo $\mathbb {Z} /n\mathbb {Z}$. En efecto, junto con el teorema de Lagrange de los posibles tamaños de subgrupos de un grupo, proporciona una demostración del teorema de Euler que dice que $a^{\varphi (n)}\equiv 1{\pmod {n}}$ para todo a coprimo con n. La función φ juega también un papel clave en la definición del sistema de cifrado RSA.

Historia, terminología y notación

Leonhard Euler introdujo la función en 1763.​​​ Sin embargo, en ese momento no eligió ningún símbolo específico para denotarla. En una publicación de 1784, Euler estudió de nuevo 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 un divisor común con él".​ Esta definición varía de la definición actual de la función totiente en D= 1 pero, por lo demás, es la misma. La notación ahora estándar​​ φ(A) proviene del tratado de Carl Friedrich Gauss de 1801 Disquisitiones arithmeticae,​​ 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, J. J. Sylvester acuñó el término totiente para esta función,​​ por lo que también se la conoce como función totiente de Euler, totiente de Euler, o el totiente de Euler. El totiente de Jordan es una generalización de la idea de Euler.

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

Primeras propiedades y cálculo de la función

Se sigue de la definición que $\varphi (1)=1$, pues el elemento (1) solo puede ser coprimo consigo mismo. Para otros números se cumple que:

1. $\varphi (p)=p-1$ si $p$ es primo.
2. $\varphi (p^{k})=(p-1)p^{k-1}$ si p es primo y k es un número natural.
3. $\varphi$ es una función multiplicativa: si m y n son primos entre sí, entonces $\varphi (mn)=\varphi (m)\varphi (n)$.

La primera propiedad se demuestra fácilmente, porque un número primo es coprimo con todos sus anteriores. Y, por tanto, existen p-1 elementos coprimos con p. En otras palabras, como p es primo solo tendrá de divisores a sí mismo y a la unidad, la cual está presente en los p-1 números anteriores a p.

Para la segunda propiedad debemos observar que si $p$ es primo solo sus múltiplos ($np$) menores que $p^{k}$ presentan un máximo común divisor con $p^{k}$ distinto de uno. Esto es, $1p,2p,3p,...,(p^{k-1})p$ son los únicos números $m$ tales que $\operatorname {mcd} (p^{k},m)\neq 1$. Como en total hay $p^{k-1}$ números que satisfacen esta propiedad, el resto de números entre 1 y $p^{k}$ solo tiene de divisor en común con $p^{k}$ a la unidad. Esto es, $\varphi (p^{k})=p^{k}-p^{k-1}=(p-1)p^{k-1}$. Nótese que esta segunda propiedad se cumple porque $p$ es primo. En efecto, si hubiera un $m\neq np$ distinto de 1 tal que $\operatorname {mcd} (p^{k},m)=a\neq 1$, entonces $a$ sería divisor de $p^{k}=p\cdot p...p$ ($k$ veces); es decir, $a$ sería una potencia (y por consiguiente múltiplo) de $p$, contradiciendo la suposición inicial $m\neq np$.

Para demostrar la tercera propiedad, sabemos que:

$\varphi (n)=n\prod _{p_{i}|n}\left(1-{\frac {1}{p_{i}}}\right)$

con p_i primo, por tanto:

$\varphi (n)\varphi (m)=mn\prod _{p_{i}|n}\left(1-{\frac {1}{p_{i}}}\right)\prod _{q_{i}|m}\left(1-{\frac {1}{q_{i}}}\right)$.

Como $\operatorname {mcd} (m,n)=1$, entonces ninguno de los primos $p_{i}$ y $q_{i}$ son iguales y la descomposición en primos de $mn$ no se ve alterada, es decir, si $m=q_{1}^{\beta _{1}}q_{2}^{\beta _{2}}...q_{k}^{\beta _{1}}$ y $n=p_{1}^{\alpha _{1}}p_{2}^{\alpha _{2}}...p_{j}^{\alpha _{j}}$ entonces la descomposición en primos será $mn=q_{1}^{\beta _{1}}q_{2}^{\beta _{2}}...q_{k}^{\beta _{1}}p_{1}^{\alpha _{1}}p_{2}^{\alpha _{2}}...p_{j}^{\alpha _{j}}$, lo cual implica que

$\varphi (mn)=mn\prod _{p_{i}|n}\left(1-{\frac {1}{p_{i}}}\right)\prod _{q_{i}|m}\left(1-{\frac {1}{q_{i}}}\right)$

por lo tanto, $\varphi (mn)=\varphi (m)\varphi (n)$ si $m$ y $n$ son primos relativos.

Con esto, el valor de φ(n) puede calcularse empleando el teorema fundamental de la Aritmética: si

$n=p_{1}^{k_{1}}\cdots p_{r}^{k_{r}}$

donde los p_j son números primos distintos, entonces

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

Esta última fórmula es un producto de Euler y a menudo se escribe como

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

donde los p son los distintos primos que dividen a n.

Ejemplo de cálculo

$\varphi (36)=\varphi \left(3^{2}2^{2}\right)=36\left(1-{\frac {1}{3}}\right)\left(1-{\frac {1}{2}}\right)=36\cdot {\frac {2}{3}}\cdot {\frac {1}{2}}=12.$

También,

$\varphi (36)=\varphi \left(3^{2}2^{2}\right)=(3-1)3^{(2-1)}(2-1)2^{(2-1)}=2\cdot 3\cdot 1\cdot 2=12.$

Se puede comprobar manualmente que los números coprimos con 36 (o sea, que no son divisibles por 2 ni por 3) son doce: 1, 5, 7, 11, 13, 17, 19, 23, 25, 29, 31, y 35.

Transformada de Fourier

El totiente es la transformada de Fourier discreta del mcd, evaluado en 1.​ Sea

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

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

La parte real de esta fórmula es

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

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

$${\begin{array}{rcl}\varphi (10)&=&mcd(1,10)\cos {\tfrac {2\pi }{10}}+mcd(2,10)\cos {\tfrac {4\pi }{10}}+mcd(3,10)\cos {\tfrac {6\pi }{10}}+\cdots +mcd(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 n y todo número entero positivo menor que n, lo que es suficiente para proporcionar la factorización de todos modos.

Divisor suma

La propiedad establecida por Gauss,​ de que

$\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 (véase función aritmética para conocer las convenciones de la notación).

Una prueba es notar 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 coprimo de k 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 elementos φ(d) de C_n, la fórmula es la siguiente.​ De manera equivalente, la fórmula se puede derivar mediante el mismo argumento aplicado al grupo multiplicativo de las raíces de unidad n-ésimas raíces de la unidad y d-esimas primitivas.

La fórmula también se puede derivar de la aritmética elemental.​ Por ejemplo, sea n = 20 y considérense las fracciones positivas hasta 1 con denominador 20:

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

Reduciéndolas a términos mínimos:

${\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 k/d ≤ 1 positivas 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, a saber, 1/20, 3/20, 7/20, 9/20, 11/20, 13/20, 17/20 y 19/20. Por definición, se trata de las φ(20) fracciones con denominador 20. 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. Se aplica un argumento similar para cualquier n.

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

$\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 $\mu (p)=-1$ y $\mu (p^{k})=0$ para cada primo p y k ≥ 2. Esta fórmula también se puede derivar de la fórmula del producto multiplicando ${\textstyle \prod _{p\mid n}(1-{\frac {1}{p}})}$ para obtener ${\textstyle \sum _{d\mid n}{\frac {\mu (d)}{d}}.}$

Un ejemplo:

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

Representación gráfica de los 100 primeros valores. Nótese que el límite inferior marcado por la recta y = 4n/15 no es el límite inferior de la función de manera global, sino para múltiplos de 30.

Los 99 primeros valores de la función vienen escritos en la siguiente tabla, así como gráficamente.

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

Propiedades

• El valor de φ(n) es igual al orden del grupo de las unidades del anillo Z/nZ (véase aritmética modular). Esto, junto con el teorema de Lagrange, proporciona una demostración del teorema de Euler.

• φ(n) también es igual al número de generadores del grupo cíclico C_n (y por ello también es igual al grado del polinomio ciclotómico Φ_n). Como cada elemento de C_n genera un subgrupo cíclico y los subgrupos de C_n son de la forma C_d donde d divide a n (notación: d|n), se tiene que

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

     donde la suma es de todos los divisores positivos d de n.

     De esta manera, se puede emplear la fórmula de inversión de Möbius para «invertir» esta suma y obtener otra fórmula para φ(n):

$\varphi (n)=\sum _{d\mid n}d\mu (n/d)$

     donde μ es la usual función de Möbius definida sobre los enteros positivos.

• La siguiente fórmula es de una serie de Dirichlet que genera un grupo cíclico φ(n):

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

Teorema de Euler

El teorema de Euler establece que si a y n son números coprimos, entonces

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

El caso especial donde n es primo se conoce como Pequeño teorema de Fermat.

Esto se deduce de Lagrange's theorem y del hecho de que φ(n) es el order de multiplicative group of integers modulo n.

El RSA cryptosystem se basa en este teorema: implica que el inverse 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 lo tanto, la dificultad de calcular d: esto se conoce como 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 (elegidos al azar) p y q. Solo n se divulga públicamente y, dado el difficulty to factor large numbers, se tiene la garantía de que nadie más conoce la factorización.

Otras fórmulas

• $a\mid b\implies \varphi (a)\mid \varphi (b)$

Teorema de Euler states that, if n and a are coprime positive integers, then

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

We just saw that $n\mid (a^{\varphi (n)}-1)\implies \varphi (n)\mid \varphi (a^{\varphi (n)}-1)$ then, if we set $m:=\varphi (n)\geq 1$ we obtain the following property,

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

Nótense los casos especiales

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

• $\varphi (\operatorname {lcm} (m,n))\cdot \varphi (\operatorname {gcd} (m,n))=\varphi (m)\cdot \varphi (n)$

Compárese esto con la fórmula

• $\operatorname {lcm} (m,n)\cdot \operatorname {gcd} (m,n)=m\cdot n$

(véase 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 ≥ 2n tal que l | φ(aⁿ − 1).
• ${\frac {\varphi (n)}{n}}={\frac {\varphi (\operatorname {rad} (n))}{\operatorname {rad} (n)}}$

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

• $\sum _{d\mid n}{\frac {\mu ^{2}(d)}{\varphi (d)}}={\frac {n}{\varphi (n)}}$ ​
• $\sum _{1\leq k\leq n \atop (k,n)=1}\!\!k={\tfrac {1}{2}}n\varphi (n)\quad {\text{for }}n>1$
• $\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)$ (​ cited in​)

• $\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)$ ​
• $\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)$ ​
• $\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)$ ​

(donde γ es el Constante de Euler-Mascheroni).

• $\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 entero positivo y ω(m) es el número de factores primos distintos de m.​​

Identidad de Menón

En 1965 P. Kesava Menon demostró

$\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.

Fórmulas que involucran la proporción áurea

Schneider​ encontró un par de identidades que conectan la función totient, número áureo y 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.

Están:

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

y

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

Restarlos da

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

La aplicación de la función exponencial a ambos lados de la identidad anterior produce una fórmula de producto infinito para e:

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

La demostración se basa en las dos fórmulas.

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

El Serie de Dirichlet para φ(n) puede escribirse en términos de Función zeta de Riemann como:​

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

donde el lado izquierdo converge para $\Re s>2$.

La función generadora Serie de Lambert es​

$\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'".​

Primero​

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

pero como n tiende a infinito,​ para todo δ > 0

${\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 divisor sum function σ(n).

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

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

verdadero para n > 1, está probado.

También tenemos​

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

Aquí γ es Euler's constant, γ = 0.577215665..., entonces e^γ = 1.7810724... y e^−γ = 0.56145948....

Probar esto no requiere del todo el teorema de los números primos.​​ Dado que log log n tiende a infinito, esta fórmula muestra que

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

De hecho, más es verdad.​​​

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

y

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

La segunda desigualdad fue mostrada por Jean-Louis Nicolas. Ribenboim dice: "El método de prueba es interesante, ya que la desigualdad se muestra primero bajo el supuesto de que Hipótesis de Riemann es verdadero, y luego bajo el supuesto contrario".​

Para el pedido promedio, tenemos​​

$\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 debido a I. M. Vinogradov y N. M. 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) mejorado el término de error a

$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). "Big O" 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 usar para demostrar​ que la probabilidad de que dos números elegidos al azar sean primos relativos es 6/Plantilla:Pi².

Relación de valores consecutivos

En 1950, Somayajulu probó​​

${\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 fortalecieron esto, probando​​ que el conjunto

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

es dense en los números reales positivos. También probaron​ que el conjunto

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

es denso en el intervalo (0,1).

Números de pacientes

Un número totient es un valor de la función totient de Euler: es decir, un m para el que hay al menos un n para el que φ(n) = m. La valencia o multiplicidad de un número total m es el número de soluciones de esta ecuación.​ Un número no totiente es un número natural que no es un número totient. Todo entero impar que exceda de 1 es trivialmente un nontotient. También hay un número infinito de no-tocientes pares,​ y, de hecho, cada entero positivo tiene un múltiplo que es un no-tociente par.​

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

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

para una constante C = 0.8178146....​

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

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

Se sabe que la multiplicidad de m supera a m^δ infinitamente a menudo para cualquier δ < 0.55655.​​

Teorema de Ford

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

Sin embargo, no se conoce ningún número m con multiplicidad k = 1. Carmichael's totient function conjecture es la afirmación de que no existe tal m.​

Aplicaciones

Ciclotomía

En la última sección del Disquisitiones​​, Gauss demuestra​ que un n-ágono regular se puede construir 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 totient dice que su totient puede ser una potencia de dos solo si n es una potencia primera y n − 1 es una potencia de 2. Los números primos que son uno más que una potencia de 2 se llaman Número de Fermat y solo se conocen cinco: 3, 5, 17, 257 y 65537 Fermat y Gauss sabían de esto. 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 números primos de Fermat distintos y cualquier potencia de 2. Los primeros n son​

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

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 divulgan al público y d (la "clave de descifrado") se mantiene en 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 usar 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

Conjetura de Lehmer

Si p es primo, entonces φ(p) = p − 1. En 1932 Derrick Henry Lehmer preguntó si hay algún número compuesto n tal que φ(n) divida a n − 1. Ninguno es conocido.​

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 probaron que n > 10²⁰ y que ω(n) ≥ 14.​ Además, Hagis demostró que si 3 divide n, entonces n > 10^1937042 y ω(n) ≥ 298848.​​

Conjetura de Carmichael

Esto establece que no hay ningún número n con la propiedad que para todos los demás números m, m ≠ n, φ(m) ≠ φ(n). Ver Ford's theorem arriba.

Como se indica en el artículo principal, si hay un solo contraejemplo a esta conjetura, debe haber un número infinito de contadores. reejemplos, y el más pequeño tiene al menos diez mil millones de dígitos en base 10.​

Hipótesis de Riemann

El Hipótesis de Riemann es verdadero si y solo si la desigualdad

${\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 Constante de Euler-Mascheroni y p₁₂₀₅₆₉# son los primos product of the first 120569.​

Véase también

• Teorema de Euler
• Función indicatriz de Jordan
• Función suma indicatriz
• Número altamente totiente
• Número altamente cototiente
• Número no totiente
• Función de Carmichael
• Conjetura de Duffin–Schaeffer
• Pequeño teorema de Fermat
• Número altamente compuesto
• Grupo multiplicativo de enteros módulo n
• Suma de Ramanujan
• Función suma indicatriz
• Función psi de Dedekind

Bibliografía

• Long, Calvin T. (1972), Elementary Introduction to Number Theory (2nd edición), Lexington: D. C. Heath and Company, LCCN 77171950 .
• Pettofrezzo, Anthony J.; Byrkit, Donald R. (1970), Elements of Number Theory, Englewood Cliffs: Prentice Hall, LCCN 77081766 .
• Long, Calvin T. (1972), Elementary Introduction to Number Theory (2nd edición), Lexington: D. C. Heath and Company, LCCN 77171950 .
• Pettofrezzo, Anthony J.; Byrkit, Donald R. (1970), Elements of Number Theory, Englewood Cliffs: Prentice Hall, LCCN 77081766 .
• Schramm, Wolfgang (2008), «The Fourier transform of functions of the greatest common divisor», Electronic Journal of Combinatorial Number Theory, A50 (8(1)) ..

Enlaces externos

• Weisstein, Eric W. «Euler's Totient Function». En Weisstein, Eric W, ed. MathWorld (en inglés). Wolfram Research. 
• EulerPhifunction en PlanetMath.
• Wikilibros alberga un libro o manual sobre Implementaciones de la función φ de Euler.

• Datos: Q190026
• Multimedia: Totient function / Q190026