Función totiente de Euler

miniatura|Os primeiros mil valores de . Os puntos da liña superior representan  cando  é un número primo, que é
En teoría de números, **a función totiente de Euler** conta os enteiros positivos ata un número enteiro dado  que son coprimos con . Escríbese usando a letra grega fi como \varphi(n) ou \phi(n), e tamén se pode chamar **función fi de Euler**. Noutras palabras, é o número de enteiros  no rango  para os que o máximo común divisor  é igual a 1.   Os números enteiros  desta forma denomínanse ás veces como *totativos* de .

Por exemplo, os totativos de  son os seis números 1, 2, 4, 5, 7 e 8. Todos son primos relativos de 9, mais os outros tres números deste rango, 3, 6 e 9 non o son, xa que  e . Polo tanto, . Un exempliño pequeno sería,  xa que para  o único enteiro no intervalo de 1 a  é o propio 1, e .

A función totiente de Euler é unha función multiplicativa, o que significa que se dous números  e  son coprimos, daquela .  Esta función dá a orde do grupo multiplicativo de enteiros módulo (o grupo de unidades do anel \Z/n\Z). Tamén se usa para definir o sistema de cifrado RSA.

## Historia, terminoloxía e notación 
Leonhard Euler introduciu a función en 1763.    Porén, non escolleu nese momento ningún símbolo específico para denotalo. Nunha publicación de 1784, Euler estudou máis a función, escollendo a letra grega  para denotala: escribiu  para "a multitude de números inferiores a , e que non teñen divisor común con ela".   A notación agora estándar   provén do tratado *Disquisitiones Arithmeticae* de Gauss de 1801, aínda que Gauss non utilizou parénteses ao redor do argumento e escribiu . Así, a miúdo chámase **función phi de Euler** ou simplemente **función fi**.

En 1879, J.J. Sylvester acuñou o termo **"totient"** para esta función,   polo que tamén se chama **función totiente de Euler**, **totiente de Euler**. 

O **cototiente de ** defínese como  n - \varphi(n) . Conta o número de enteiros positivos inferiores ou iguais a  que teñen polo menos un factor primo en común con .

## Cálculo da función totiente de Euler 
Hai varias fórmulas para calcular  .

### Fórmula do produto de Euler 
: \varphi(n) =n \prod_{p\mid n} \left(1-\frac{1}{p}\right),

onde o produto é sobre os distintos números primos que dividen . (Para notación, consulte Función aritmética).

Unha formulación equivalente é \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), 

onde n = p_1^{k_1} p_2^{k_2} \cdots p_r^{k_r} é a descomposición en factores primos de n (é dicir, p_1, p_2,\ldots,p_r son números primos distintos).

A proba destas fórmulas depende de dous feitos importantes:

#### Fi é unha función multiplicativa 
Isto significa que se , daquela . 

*Esquema de demostración:* Sexan , ,  os conxuntos de enteiros positivos que son coprimos e inferiores a , , , respectivamente, de xeito que , etc. Entón hai unha bixección entre  e  polo teorema chinés do resto.

#### Valor de fi para un argumento que sexa potencia dun primo 
Se  é primo e , daquela

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

#### Proba da fórmula do produto de Euler 
O teorema fundamental da aritmética estabelece que se  hai unha expresión única n = p_1^{k_1} p_2^{k_2} \cdots p_r^{k_r},  onde  son números primos e cada . (O caso  corresponde ao produto baleiro) Usando repetidamente a propiedade multiplicativa de  e a fórmula para  dá

: \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}

Isto dá ambas as versións da fórmula do produto de Euler.

#### Exemplo 
: \varphi(20)=\varphi(2^2 5)=20\,(1-\tfrac12)\,(1-\tfrac15)
=20\cdot\tfrac12\cdot\tfrac45=8.

A fórmula alternativa usa só números enteiros,
: \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 
O totiente é a transformada discreta de Fourier do mcd, avaliada en 1.  Sexa

:  \mathcal{F} \{ \mathbf{x} \}[m] = \sum\limits_{k=1}^n x_k \cdot e^{{-2\pi i}\frac{mk}{n}}

onde  para {{Math|*k* ∈ {1, ..., *n*}}}. Daquela

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

A parte real desta fórmula é

: \varphi (n)=\sum\limits_{k=1}^n \gcd(k,n) \cos {\tfrac{2\pi k}{n}}
.

Por exemplo, usando \cos\tfrac{\pi}5 = \tfrac{\sqrt 5+1}4
 e \cos\tfrac{2\pi}5 = \tfrac{\sqrt 5-1}4
 : \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{\sqrt5+1}4) + 2\cdot(\tfrac{\sqrt5-1}4) + 
1\cdot(-\tfrac{\sqrt5-1}4) + 2\cdot(-\tfrac{\sqrt5+1}4) + 5\cdot (-1) \\
&& +\ 2\cdot(-\tfrac{\sqrt5+1}4) + 1\cdot(-\tfrac{\sqrt5-1}4) + 2\cdot(\tfrac{\sqrt5-1}4) +
1\cdot(\tfrac{\sqrt5+1}4) + 10 \cdot (1) \\
&=& 4 .
\end{array}
 A diferenza do produto de Euler e da fórmula da suma dos divisores esta fórmula non require coñecer os factores de . Porén, implica o cálculo do máximo común divisor de  e de cada número enteiro positivo menor que , o que é abondo para proporcionar a factorización e por tanto estamos nun grao de dificultade similar para calcular o valor da función.

### Suma de divisores 
A propiedade estabelecida por Gauss para os divisores  dun número  di 

: \sum_{d\mid n}\varphi(d)=n.

A inversión de Möbius aplicada á fórmula da suma de divisores dá

:  \varphi(n) = \sum_{d\mid n} \mu\left( d \right) \cdot \frac{n}{d} = n\sum_{d\mid n} \frac{\mu (d)}{d},

onde  é a función de Möbius, función multiplicativa definida por \mu(p) = -1 e  \mu(p^k) = 0 para cada primo  e . Esta fórmula tamén se pode derivar da fórmula do produto realizando ese produto  \prod_{p\mid n} (1 - \frac{1}{p})  para conseguir  \sum_{d \mid n} \frac{\mu (d)}{d}. 

Un exemplo: 
: 
 \begin{align}
\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{align}

## Algúns valores 
Os primeiros 100 valores  móstranse na táboa e no gráfico a continuación:
miniatura| Gráfico dos 100 primeiros valores
:
Na gráfica da dereita, a liña superior  é un límite superior válido para tódolos  distintos de 1, e acadado se e só se  é un número primo. Un límite inferior simple é \varphi(n) \ge \sqrt{n/2} , que ten bastante marxe.

## Teorema de Euler 
O teorema de Euler indica que se  e  son primos relativos, daquela

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

O caso especial onde  é primo coñécese como pequeno teorema de Fermat.

Isto dedúcese do teorema de Lagrange e do feito de que  é a orde do grupo multiplicativo de enteiros módulo .

## Outras fórmulas 
* a\mid b \implies \varphi(a)\mid\varphi(b)
*  m \mid \varphi(a^m-1)
* \varphi(mn) = \varphi(m)\varphi(n)\cdot\frac{d}{\varphi(d)} \quad\text{onde }d = \operatorname{gcd}(m,n) En particular:
** \varphi(2m) = \begin{cases}
2\varphi(m) &\text{ if } m \text{ é par} \\
\varphi(m) &\text{ if } m \text{ é impar}
\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) Comparar isto coa fórmula \operatorname{lcm}(m,n)\cdot \operatorname{gcd}(m,n) = m \cdot n  (ver Mínimo común múltiplo).
*  é par para . A maiores, se  ten  factores  primos impares distintos, .
* Para todo  e  tal que  existe un  tal que .
* \frac{\varphi(n)}{n}=\frac{\varphi(\operatorname{rad}(n))}{\operatorname{rad}(n)}. Onde  é o radical de . (O produto de todos os números primos distintos que dividen ).
* \sum_{d \mid n} \frac{\mu^2(d)}{\varphi(d)} = \frac{n}{\varphi(n)} 
* \sum_{1\le k\le n-1 \atop gcd(k,n)=1}\!\!k = \tfrac12 n\varphi(n) \quad \text{para }n>1
* \sum_{k=1}^n\varphi(k) = \tfrac12 \left(1+ \sum_{k=1}^n \mu(k)\left\lfloor\frac{n}{k}\right\rfloor^2\right)
=\frac3{\pi^2}n^2+O\left(n(\log n)^\frac23(\log\log n)^\frac43\right)( citado en)
* \sum_{k=1}^n\varphi(k) =\frac3{\pi^2}n^2+O\left(n(\log n)^\frac23(\log\log n)^\frac13\right)  [Liu (2016)] 
* \sum_{k=1}^n\frac{\varphi(k)}{k} = \sum_{k=1}^n\frac{\mu(k)}{k}\left\lfloor\frac{n}{k}\right\rfloor=\frac6{\pi^2}n+O\left((\log n)^\frac23(\log\log n)^\frac43\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)^\frac23}n\right);

: \sum_{n=1}^\infty \frac{\varphi(n)}{n^s}=\frac{\zeta(s-1)}{\zeta(s)}

onde o lado esquerdo converxe para \Re (s)>2 .

A función xeradora da serie de Lambert é 

: \sum_{n=1}^{\infty} \frac{\varphi(n) q^n}{1-q^n}= \frac{q}{(1-q)^2}

que converxe para .

## Taxa de crecemento 
Segundo as palabras de Hardy e Wright, a orde de  é "sempre case ".

Primeiro 

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

mais cando *n* vai ao infinito,  para todo 

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

Estas dúas fórmulas pódense probar usando pouco máis que as fórmulas para  e a función suma de divisores  .

De feito, durante a proba da segunda fórmula, próbase a desigualdade

: \frac {6}{\pi^2} .

Tamén temos que 

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

Aquí  é a constante de Euler-Mascheroni,  , polo que  e  .

Para a orde media, temos 

: \varphi(1)+\varphi(2)+\cdots+\varphi(n) = \frac{3n^2}{\pi^2}+O\left(n(\log n)^\frac23(\log\log n)^\frac43\right) \quad\text{cando }n\rightarrow\infty,

debido a Arnold Walfisz, a súa proba aproveita estimacións sobre sumas exponenciais debidas a I.M. Vinogradov e N.M. Korobov. Por unha combinación dos métodos de van der Corput e Vinogradov, H.-Q. Liu (Sobre a función de Euler.Proc. Roy. Soc. Edinburgh Sect. A 146 (2016), no 4, 769–775) mellorou o termo de erro a

: 
O\left(n(\log n)^\frac23(\log\log n)^\frac13\right) 

(esta é ata 2024 a mellor estimación coñecida deste tipo). A notación " grande" representa unha cantidade que está limitada por unha constante multiplicada pola función de  dentro dos parénteses (que é pequena en comparación con ).

Este resultado pódese usar para demostrar  que a probabilidade de que dous números escollidos aleatoriamente sexan coprimos é , que é a recíproca da zeta de Riemann de 2, igual a 1/\zeta(2).

## Ratio de valores consecutivos 
En 1950 Somayajulu demostrou  

: \begin{align}
\lim\inf \frac{\varphi(n+1)}{\varphi(n)}&= 0 \quad\text{e} \\[5px]
\lim\sup \frac{\varphi(n+1)}{\varphi(n)}&= \infty.
\end{align}

En 1954 Schinzel e Sierpiński reforzaron isto, demostrando   que o conxunto

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

é denso nos números reais positivos. Tamén demostraron  que o conxunto

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

é denso no intervalo (0,1).

## Números totientes 
Un **número totiente** é un valor da función totiente de Euler: é dicir, un  para o cal hai polo menos un  para o cal  . A *valencia* ou *multiplicidade* dun número totiente  é o número de solucións desa ecuación. Un *número non totiente* é un número natural que non é un número totiente. Todo número enteiro impar que exceda 1 é trivialmente un non totiente. Tamén hai infinitos non totientes pares,  e de feito cada número enteiro positivo ten un múltiplo que é un non totiente par. 
O número de números totientes ata un límite dado  é

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

para unha constante . 

Se se conta segundo a multiplicidade, o número de números totientes ata un determinado límite  é

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

onde o termo de erro  é de orde como máximo  \frac{x}{(\log{x})^k}.

## Aplicacións 
### Ciclotomía 
Na última sección das *Disquisitiones*   Gauss demostra  que un -gono regular pode construírse con regra e compás se  é unha potencia de 2. Se  é unha potencia dun número primo impar, a fórmula para o totiente di que o seu totiente pode ser unha potencia de dous só se  é unha primeira potencia e  é unha potencia de 2. Os primos que son un máis que unha potencia de 2 chámanse primos de Fermat e só se coñecen cinco: 3, 5, 17, 257 e 65537. Fermat e Gauss sabían destes. Ninguén puido demostrar se hai máis.

Así, un -gono regular ten unha construción con escadro e compás se *n* é un produto de distintos números primos de Fermat e calquera potencia de 2. Os primeiros  son 

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

### Teorema dos números primos para progresións aritméticas 
### O criptosistema RSA 
Configurar un sistema RSA implica escoller grandes números primos  e , calcular  e  e atopar dous números  e  tal que . Os números  e  (a "chave de cifrado") son liberados ao público, e  (a "chave de descifrado") mantense en privado.

Unha mensaxe, representada por un número enteiro , onde , encriptase calculando .

Descífrase calculando . O teorema de Euler pódese usar para demostrar que se , daquela  .

A seguridade dun sistema RSA veríase comprometida se o número  puidese factorizarse eficientemente ou se  puidese calcularse eficientemente sen factorizar .

## Problemas sen resolver 
### Conxectura de Lehmer 
Se  é primo, daquela . En 1932 D. H. Lehmer preguntou se hai números compostos  tal que  divide a . Non se coñece ningún. 

En 1933 demostrou que se existe algún  dese tipo, debe ser impar, libre de cadrados e divisíbel por polo menos sete números primos (é dicir,  ). En 1980 Cohen e Hagis demostraron que  e que . Alén diso, Hagis demostrou que se 3 divide  logo  e .

### A conxectura de Carmichael 
Di que non hai un número  coa propiedade de que para todos os demais números , , . 

Como se indica no artigo principal, se hai un único contraexemplo para esta conxectura, debe haber infinitos contraexemplos, e o máis pequeno ten polo menos dez mil millóns de díxitos en base 10.

### Hipótese de Riemann 
A hipótese de Riemann é certa se e só se a desigualdade

: \frac{n}{\varphi (n)}

é certa para todos os  onde  é a constante de Euler-Macheroni e  é o  produto dos primeiros  primos.

## Notas 
## Véxase tamén 
### Bibliografía 
*. See paragraph 24.3.2.
*
* Dickson, Leonard Eugene, "History Of The Theory Of Numbers", vol 1, chapter 5 "Euler's Function, Generalizations; Farey Series", Chelsea Publishing 1952
*.
*
*
*
* 
*
*.
* 
* 
*
*
* 
* 
*.
### Outros artigos 
*Función de Carmichael (λ)
*Función psi de Dedekind (𝜓)
*Función divisor (σ)

*Conxectura de Duffin–Schaeffer
*Pequeno teorema de Fermat
*Número altamente composto
*Grupo multiplicativo de enteiros módulo n
*Suma de Ramanujan
*Función sumatoria totiente (𝛷)

### Ligazóns externas 
* 
*Euler's Phi Function and the Chinese Remainder Theorem — proof that  is multiplicative 
*Euler's totient function calculator in JavaScript — up to 20 digits
*Dineva, Rosica, The Euler Totient, the Möbius, and the Divisor Functions 
*Plytage, Loomis, Polhill Summing Up The Euler Phi Function