Función φ de Euler

Los primeros mil valores de $\phi (n)$.

La función φ de Euler (también llamada 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:

$\phi (n)=|\{m\in \mathbb{N}|m\le n\wedge \mathrm{m}\mathrm{c}\mathrm{d}(m,n)=1\}|$

donde |·| significa la cardinalidad del conjunto descrito.

Otra forma de definir el totiente de un número natural n es indicar que es la cantidad de números enteros positivos menores que n tales que el máximo común divisor con respecto a n es igual a 1.

La función φ es importante principalmente porque proporciona el tamaño del grupo multiplicativo de enteros módulo n. Más precisamente, $\phi (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^{\phi (n)}\equiv 1(\mathrm{mod}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 Plantilla:Mvar para denotarla: escribió Plantilla:Math para "la multitud de números menores que Plantilla:Mvar, 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 Plantilla:Math pero, por lo demás, es la misma. La notación ahora estándar Plantilla:Math proviene del tratado de Carl Friedrich Gauss de 1801 Disquisitiones arithmeticae, aunque Gauss no usó paréntesis alrededor del argumento y escribió Plantilla:Math. 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-\phi (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 $\phi (1)=1$, pues el elemento $1$ sólo puede ser coprimo consigo mismo. Para otros números se cumple que:

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

La primera propiedad se demuestra fácilmente, porque un número primo es coprimo con todos sus números anteriores. Y, por tanto, existen $p-1$ elementos coprimos con $p$. En otras palabras, como $p$ es primo sólo 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 sólo sus múltiplos $np$ menores o iguales que $p^k$ presentan un 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 $\mathrm{m}\mathrm{c}\mathrm{d}(p^k,m)\ne 1$. Como en total hay $p^{k-1}$ números que satisfacen esta propiedad, el resto de números entre $1$ y $p^k$ sólo tienen a $1$ como divisor común con $p^k$. Esto es, $\phi (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\ne np$, $m\ge 2$ tal que $\mathrm{m}\mathrm{c}\mathrm{d}(p^k,m)=a\ne 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\ne np$).

Para demostrar la tercera propiedad, sean $A$, $B$, $C$ los conjuntos de enteros positivos que son coprimos y menores que $m$, $n$, $mn$ respectivamente ( entonces $|A|=\phi (m)$, $|B|=\phi (n)$ y $|C|=\phi (mn)$ ). Luego, por el Teorema Chino del Resto existe una biyección entre $C$ y $A\times B$, lo que implica que $\phi (mn)=\phi (m)\phi (n)$.

Con esto, el valor de $\phi (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

$\phi (n)=(p_1-1)p_1^{k_1-1}\cdots (p_r-1)p_r^{k_r-1}.$

Esta fórmula puede reescribirse de la siguiente manera (conocida como la Fórmula de Producto de Euler):

$\phi (n)=n\prod _{p|n}(1-\frac{1}{p})$

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

Ejemplo de cálculo

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

También,

$\phi (36)=\phi \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

$ℱ\{𝐱\}[m]=\sum _{k=1}^n{x}_k\cdot e^{-2\pi i\frac{mk}{n}}$

donde Plantilla:Math para Plantilla:Math. Entonces

$\phi (n)=ℱ\{𝐱\}[1]=\sum _{k=1}^n\mathrm{mcd}(k,n)e^{-2\pi i\frac{k}{n}}.$

La parte real de esta fórmula es

$\phi (n)=\sum _{k=1}^n\mathrm{mcd}(k,n)\cos \frac{2\pi k}{n}$

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

Suma de sus divisores

La propiedad establecida por Gauss, de que

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

donde la suma es sobre todos los divisores positivos Plantilla:Mvar de Plantilla:Mvar, 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 Plantilla:Math también es igual al número de posibles generadores del grupo cíclico Plantilla:Math; específicamente, si Plantilla:Math con Plantilla:Math, entonces Plantilla:Math es un generador para cada coprimo de Plantilla:Mvar a Plantilla:Mvar. Dado que cada elemento de Plantilla:Math genera un subgrupo cíclico, y todos los subgrupos Plantilla:Math son generados precisamente por elementos Plantilla:Math de Plantilla:Math, 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 Plantilla:Mvar-ésimas raíces de la unidad y Plantilla:Mvar-ésimas primitivas.

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

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

Reduciéndolas a términos mínimos:

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

Estas veinte fracciones son todas las Plantilla:Sfrac ≤ 1 positivas cuyos denominadores son los divisores Plantilla:Math. Las fracciones con 20 como denominador son aquellas con numeradores relativamente primos a 20, a saber, Plantilla:Sfrac, Plantilla:Sfrac, Plantilla:Sfrac, Plantilla:Sfrac, Plantilla:Sfrac, Plantilla:Sfrac, Plantilla:Sfrac y Plantilla:Sfrac. Por definición, se trata de las Plantilla:Math fracciones con denominador 20. De manera similar, hay Plantilla:Math fracciones con denominador 10 y Plantilla:Math fracciones con denominador 5, etc. Por lo tanto, el conjunto de veinte fracciones se divide en subconjuntos de tamaño Plantilla:Math para cada Plantilla:Math 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

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

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

Un ejemplo:

$\begin{array}{cc}\phi (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\\ & =1\cdot 20-1\cdot 10+0\cdot 5-1\cdot 4+1\cdot 2+0\cdot 1=8.\end{array}$

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.

$\phi (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

Teorema de Euler

El teorema de Euler establece que si Plantilla:Mvar y Plantilla:Mvar son números coprimos, entonces

$a^{\phi (n)}\equiv 1modn.$

El caso especial donde Plantilla:Mvar es primo se conoce como el pequeño teorema de Fermat.

Esto se deduce del teorema de Lagrange y del hecho de que Plantilla:Math es el orden del [[Grupo multiplicativo de enteros módulo n|grupo multiplicativo de enteros módulo Plantilla:Mvar]].

El sistema de encriptado RSA se basa en este teorema: implica que el inverso de la función Plantilla:Math, donde Plantilla:Mvar es el exponente de cifrado (público), es la función Plantilla:Math, donde Plantilla:Mvar, el exponente de descifrado (privado), es el inverso multiplicativo de Plantilla:Mvar módulo Plantilla:Math . La dificultad de calcular Plantilla:Math sin conocer la factorización de Plantilla:Mvar es, por lo tanto, la dificultad de calcular Plantilla:Mvar: esto se conoce como el problema RSA, que se puede resolver factorizando Plantilla:Mvar. El propietario de la clave privada conoce la factorización, ya que una clave privada RSA se construye eligiendo Plantilla:Mvar como el producto de dos números primos grandes (elegidos al azar) Plantilla:Mvar y Plantilla:Mvar. Solo Plantilla:Mvar se divulga públicamente y, dada la dificultad de factorizar números muy largos, se tiene la garantía de que nadie más conocerá la factorización.

Otras fórmulas

• $a\mid b⟹\phi (a)\mid \phi (b)$
• $n\mid \phi (a^n-1)$ ( $n,a\in \mathbb{N}$ , $a\ge 2$ ) : Sea $m=a^n-1$ . Entonces tenemos que:

$\mathrm{mcd}(a,m)=\mathrm{mcd}(a,a^n-1)=\mathrm{mcd}(a,1)=1\Rightarrow a\in {\mathbb{Z}}_m^{*}\Rightarrow <a>\subset {\mathbb{Z}}_m^{*}$ . Luego, por el Teorema de Lagrange, $|<a>|$ divide a $|{\mathbb{Z}}_m^{*}|$ .

$$Pero $a^k<m$ si $k<n\Rightarrow |<a>|=n$ , y además $|{\mathbb{Z}}_m^{*}|=\phi (m)$ .

$$Por lo tanto, $n\mid \phi (m)\Rightarrow n\mid \phi (a^n-1)$

• $\phi (mn)=\phi (m)\phi (n)\cdot \frac{d}{\phi (d)}$ , donde $d=\mathrm{mcd}(m,n)$

$$Nótense los casos especiales:

• $\phi (2m)=\{\begin{array}{cc}2\phi (m)& \text{ si }m\text{ es par}\\ \phi (m)& \text{ si }m\text{ es impar}\end{array}$
• $\phi \left(n^m\right)=n^{m-1}\phi (n)$
• $\phi (\mathrm{mcm}(m,n))\cdot \phi (\mathrm{mcd}(m,n))=\phi (m)\cdot \phi (n)$

$\to$ Compárese esto con la fórmula $\mathrm{mcm}(m,n)\cdot \mathrm{mcd}(m,n)=m\cdot n$ (véanse mínimo común múltiplo (mcm) y máximo común divisor (mcd)).

• Plantilla:Math es par para Plantilla:Math. Además, si Plantilla:Mvar tiene Plantilla:Mvar factores primos impares distintos, Plantilla:Math
• Para cualquier Plantilla:Math y Plantilla:Math tal que Plantilla:Math existe un Plantilla:Math tal que Plantilla:Math.
• $\frac{\phi (n)}{n}=\frac{\phi (\mathrm{rad}(n))}{\mathrm{rad}(n)}$ ,

$$donde Plantilla:Math es el [[Radical de un entero|radical de Plantilla:Mvar]] (el producto de todos los primos distintos que dividen Plantilla:Mvar).

• $\sum _{d\mid n}\frac{{\mu }^2(d)}{\phi (d)}=\frac{n}{\phi (n)}$ 
• $\sum _{\genfrac{}{}{0ex}{}{1\le k\le n}{(k,n)=1}}k=\frac{1}{2}n\phi (n)\text{ para }n>1$
• $\sum _{k=1}^n\phi (k)=\frac{1}{2}(1+\sum _{k=1}^n\mu (k){\lfloor \frac{n}{k}\rfloor }^2)=\frac{3}{{\pi }^2}{n}^2+O(n(\log n{)}^{\frac{2}{3}}(\log \log n{)}^{\frac{4}{3}})$ ( citado en)
• $\sum _{k=1}^n\frac{\phi (k)}{k}=\sum _{k=1}^n\frac{\mu (k)}{k}\lfloor \frac{n}{k}\rfloor =\frac{6}{{\pi }^2}n+O((\log n{)}^{\frac{2}{3}}(\log \log n{)}^{\frac{4}{3}})$ 
• $\sum _{k=1}^n\frac{k}{\phi (k)}=\frac{315\zeta (3)}{2{\pi }^4}n-\frac{\log n}{2}+O((\log n{)}^{\frac{2}{3}})$ 
• $\sum _{k=1}^n\frac{1}{\phi (k)}=\frac{315\zeta (3)}{2{\pi }^4}(\log n+\gamma -\sum _{p\text{ primo }}\frac{\log p}{p^2-p+1})+O\left(\frac{(\log n{)}^{\frac{2}{3}}}{n}\right)$&thinsp,

$$donde Plantilla:Mvar es la constante de Euler-Mascheroni.

• $\sum _{\stackrel{1\le k\le n}{\mathrm{mcd}(k,m)=1}}1=n\frac{\phi (m)}{m}+O\left(2^{\omega (m)}\right)$ ,

$$donde Plantilla:Math es un entero positivo y Plantilla:Math es el número de factores primos distintos de Plantilla:Mvar.

Identidad de Menon

En 1965, P. Kesava Menon demostró que

$\sum _{\stackrel{1\le k\le n}{\mathrm{mcd}(k,n)=1}}\mathrm{mcd}(k-1,n)=\phi (n)d(n)$ ,

donde Plantilla:Math es el número de divisores de Plantilla:Mvar.

Fórmulas que involucran la proporción áurea

Schneider encontró un par de identidades que conectan la función totiente, el número áureo y la función de Möbius Plantilla:Math. En esta sección, Plantilla:Math es la función totiente y Plantilla:Math es la proporción áurea.

Se tiene que:

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

y

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

Si se restan, se obtiene

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

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

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

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

$\begin{array}{cc}\sum _{k=1}^{\mathrm{\infty }}\frac{\phi (k)}{k}(-\log (1-x^k))& =\frac{x}{1-x}\\ \text{y}\sum _{k=1}^{\mathrm{\infty }}\frac{\mu (k)}{k}(-\log (1-x^k))& =x,\text{ para }0<x<1.\end{array}$

Funciones generadoras

La serie de Dirichlet para Plantilla:Math puede escribirse en términos de la función zeta de Riemann como:

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

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

La función generadora de la serie de Lambert es

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

que converge para Plantilla:Math.

Ambas fórmulas se demuestran mediante manipulaciones de series elementales y las fórmulas para Plantilla:Math.

Tasa de crecimiento

En palabras de Hardy & Wright, el orden de Plantilla:Math es "siempre «casi Plantilla:Mvar»".

Primero

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

pero como n tiende a infinito, para todo Plantilla:Math

$\frac{\phi (n)}{n^{1-\delta }}\to \mathrm{\infty }.$

Estas dos fórmulas se pueden probar usando poco más que las fórmulas para Plantilla:Math y la función suma de divisores Plantilla:Math.

De hecho, durante la demostración de la segunda fórmula, la desigualdad

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

verdadera para Plantilla:Math, está probada.

También se tiene que

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

Aquí Plantilla:Mvar es la constante de Euler, Plantilla:Math, entonces Plantilla:Math y Plantilla:Math.

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

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

Y de hecho, se comprueban más propiedades, como

$\phi (n)>\frac{n}{e^{\gamma }\log \log n+\frac{3}{\log \log n}}\text{ para }n\ge 3$

y

$\phi (n)<\frac{n}{e^{\gamma }\log \log n}\text{ para infinitamente muchos }n.$

La segunda desigualdad fue demostrada por Jean-Louis Nicolas. Ribenboim señaló que: "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, y luego bajo el supuesto contrario".Plantilla:Rp

Para el orden promedio, se tiene que

$\phi (1)+\phi (2)+\cdots +\phi (n)=\frac{3n^2}{{\pi }^2}+O(n(\log n{)}^{\frac{2}{3}}(\log \log n{)}^{\frac{4}{3}})\text{ como }n\to \mathrm{\infty },$

Este resultado, debido a Arnold Walfisz, se demostró explotando las estimaciones sobre sumas exponenciales debidas 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) mejoró el término de error hasta

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

(esta es actualmente la mejor estimación conocida de este tipo). La cota [[Cota superior asintótica|"Big Plantilla:Mvar"]] representa una cantidad que está limitada por una constante multiplicada por la función de Plantilla:Mvar dentro de los paréntesis (que es pequeña en comparación con Plantilla:Math).

Este resultado se puede usar para demostrar que la probabilidad de que dos números elegidos al azar sean primos relativos es Plantilla:Sfrac.

Relación entre valores consecutivos

En 1950, Somayajulu probó que

$\begin{array}{cc}\lim \inf \frac{\phi (n+1)}{\phi (n)}& =0\text{y}\\ [5px]\lim \sup \frac{\phi (n+1)}{\phi (n)}& =\mathrm{\infty }.\end{array}$

En 1954 Schinzel y Sierpiński fortalecieron esta proposición, probando que el conjunto

$\{\frac{\phi (n+1)}{\phi (n)},n=1,2,\dots \}$

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

$\{\frac{\phi (n)}{n},n=1,2,\dots \}$

es denso en el intervalo (0,1).

Números totientes

Un número totiente es un valor de la función totiente de Euler: es decir, un Plantilla:Mvar para el que hay al menos un Plantilla:Mvar para el que Plantilla:Math. La valencia o multiplicidad de un número totiente Plantilla:Mvar 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 totiente. Todo entero impar que exceda de 1 es trivialmente un número no totiente. También hay un número infinito de no totientes pares, y, de hecho, cada entero positivo tiene un múltiplo que es un no totiente par.

La cantidad de números totientes hasta un límite dado Plantilla:Mvar es

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

para una constante Plantilla:Math.

Si se contabilizan de acuerdo con su multiplicidad, el número de números totientes hasta un límite dado Plantilla:Mvar es

$|\{n:\phi (n)\le x\}|=\frac{\zeta (2)\zeta (3)}{\zeta (6)}\cdot x+R(x)$

donde el término de error Plantilla:Mvar es de orden como máximo de Plantilla:Math para cualquier Plantilla:Mvar positivo.

Se sabe que la multiplicidad de Plantilla:Mvar supera a Plantilla:Math infinitamente a menudo para cualquier Plantilla:Math.

Teorema de Ford

Plantilla:Harvtxt demostró que para todo entero Plantilla:Math existe un número totiente Plantilla:Mvar de multiplicidad Plantilla:Mvar: es decir, para el cual la ecuación Plantilla:Math tiene exactamente Plantilla:Mvar soluciones; este resultado había sido previamente conjeturado por Wacław Sierpiński, y se había obtenido como consecuencia de la hipótesis H de Schinzel. De hecho, cada multiplicidad que se produce, lo hace infinitamente a menudo.

Sin embargo, no se conoce ningún número Plantilla:Mvar con multiplicidad Plantilla:Math. La conjetura de la función totiente de Carmichael es la afirmación de que no existe tal Plantilla:Mvar.

Números totientes perfectos

Los números totientes perfectos son aquellos que son iguales a la suma de sus totientes sucesivos. Existe una familia de estos números relacionados con las potencias de tres, así como con los productos de estas potencias por algunos números primos.

Aplicaciones

Ciclotomía

En la última sección de las Disquisitiones, Gauss demostró que un Plantilla:Mvar-ágono regular se puede construir con regla y compás si Plantilla:Math es una potencia de 2. Si Plantilla:Mvar 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 Plantilla:Mvar es una potencia primera y Plantilla:Math es una potencia de 2. Los números primos que son uno más que una potencia de 2 se llaman números primos de Fermat y solo se conocen cinco: 3, 5, 17, 257 y 65537. Fermat y Gauss conocían estos datos, y posteriormente nadie ha podido comprobar si hay más de estos números.

Por lo tanto, un Plantilla:Mvar-ágono regular tiene una construcción con regla y compás si n es un producto de números primos de Fermat distintos y cualquier potencia de 2. Los primeros Plantilla:Mvar son

2, 3, 4, 5, 6, 8, 10, 12, 15, 16, 17, 20, 24, 30, 32, 34, 40,... Plantilla:OEIS.

El criptosistema RSA

Configurar un sistema RSA implica elegir dos números primos grandes Plantilla:Mvar y Plantilla:Mvar, calcular Plantilla:Math y Plantilla:Math y encontrar dos números Plantilla:Mvar y Plantilla:Mvar tales que Plantilla:Math. Los números Plantilla:Mvar y Plantilla:Mvar (la "clave de cifrado") se divulgan al público y Plantilla:Mvar (la "clave de descifrado") se mantiene en privado.

Un mensaje, representado por un número entero Plantilla:Mvar, donde Plantilla:Math, se cifra calculando Plantilla:Math.

Y se descifra calculando Plantilla:Math. El teorema de Euler se puede usar para demostrar que si Plantilla:Math, entonces Plantilla:Math.

La seguridad de un sistema RSA se vería comprometida si el número Plantilla:Mvar pudiera factorizarse eficientemente o si Plantilla:Math pudiera calcularse eficientemente sin factorizar Plantilla:Mvar.

Problemas no resueltos

Conjetura de Lehmer

Si Plantilla:Mvar es primo, entonces Plantilla:Math. En 1932 Derrick Henry Lehmer planteó la cuestión de si hay algún número compuesto Plantilla:Mvar tal que Plantilla:Math divida a Plantilla:Math. No se conoce ninguno.

En 1933 demostró que si existe tal Plantilla:Mvar, debe ser impar, sin cuadrados y divisible por al menos siete números primos (es decir, Plantilla:Math). En 1980 Cohen y Hagis probaron que Plantilla:Math y que Plantilla:Math. Además, Hagis demostró que si 3 divide a Plantilla:Mvar, entonces Plantilla:Math y Plantilla:Math.

Conjetura de Carmichael

Este enunciado establece que no hay ningún número Plantilla:Mvar con la propiedad de que para todos los demás números Plantilla:Mvar, Plantilla:Math, Plantilla:Math. Véase el teorema de Ford más arriba.

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

Hipótesis de Riemann

La hipótesis de Riemann es verdadera si y solo si la desigualdad

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

es cierta para todo Plantilla:Math, donde Plantilla:Mvar es la constante de Euler-Mascheroni y Plantilla:Math es el producto de los primeros Plantilla:Math números primos.

Bibliografía

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

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

• Plantilla:Citation. See paragraph 24.3.2.
• Plantilla:Citation
• Dickson, Leonard Eugene, "History Of The Theory Of Numbers", vol 1, chapter 5 "Euler's Function, Generalizations; Farey Series", Chelsea Publishing 1952
• Plantilla:Citation.
• Plantilla:Citation
• Plantilla:Citation
• Plantilla:Citation
• Plantilla:Citation
• Plantilla:Citation
• Plantilla:Citation
• Plantilla:Citation
• Plantilla:Citation
• Plantilla:Citation
• Plantilla:Citation
• Plantilla:Cite book
• Plantilla:Citation.

Enlaces externos

• Plantilla:MathWorld
• Plantilla:PlanetMath