Función totiente de Euler

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  ou , 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 ).Ver Teorema de Euler. 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.  Sandifer, p. 203 Graham et al. p. 133 note 111 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". L. Euler, Speculationes circa quasdam insignes proprietates numerorum, Acta Academiae Scientarum Imperialis Petropolitinae, vol. 4, (1784), pp. 18–30, or Opera Omnia, Series 1, volume 4, pp. 105–115. (O traballo foi presentado na Academia de San Petersburgo no 9 de outubro do 1775).  A notación agora estándar  Both  and  are seen in the literature. These are two forms of the lower-case Greek letter phi.  provén do tratado Disquisitiones Arithmeticae de Gauss de 1801,Gauss, Disquisitiones Arithmeticae article 38 aínda que Gauss non utilizou parénteses ao redor do argumento e escribiu . Así, a miúdo chámase función phi de EulerAínda que en galego a letra grega escríbese fi deixamos phi nalgúns nomes por ser máis facilmente identificábel cos nomes noutras linguas ou simplemente función fi.

En 1879, J.J. Sylvester acuñou o termo "totient" para esta función, J. J. Sylvester (1879) "On certain ternary cubic-form equations", American Journal of Mathematics, 2 : 357-393; Sylvester coins the term "totient" on page 361.  polo que tamén se chama función totiente de Euler, totiente de Euler. 

O cototiente de  defínese como . 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 



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

Unha formulación equivalente é  

onde  é a descomposición en factores primos de  (é dicir,  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



 Proba da fórmula do produto de Euler 
O teorema fundamental da aritmética estabelece que se  hai unha expresión única  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á



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

 Exemplo 



A fórmula alternativa usa só números enteiros,


 Transformada de Fourier 
O totiente é a transformada discreta de Fourier do mcd, avaliada en 1.  Sexa



onde  para . Daquela



A parte real desta fórmula é



Por exemplo, usando  e  :  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  diGauss, DA, art 39 

 .

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



onde  é a función de Möbius, función multiplicativa definida por  e  para cada primo  e . Esta fórmula tamén se pode derivar da fórmula do produto realizando ese produto  para conseguir 

Un exemplo: 


 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
{| class="wikitable" style="text-align: right"
|+ para 
! +
! 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 || 16 || 6 || 18 || 8 
|- 
! 20
| 12 || 10 || 22 || 8 || 20 || 12 || 18 || 12 || 28 || 8 
|-
! 30
| 30 || 16 || 20 || 16 || 24 || 12 || 36 || 18 || 24 || 16 
|-
! 40
| 40 || 12 || 42 || 20 || 24 || 22 || 46 || 16 || 42 || 20
|-
! 50
| 32 || 24 || 52 || 18 || 40 || 24 || 36 || 28 || 58 || 16 
|-
! 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 
|}
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 é , que ten bastante marxe.

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



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 



  En particular:


  Comparar isto coa fórmula   (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 .
 . Onde  é o radical de . (O produto de todos os números primos distintos que dividen ).


 ( citado en)
  [Liu (2016)] 

 ;
 ;(onde  é a constante de Euler–Mascheroni).

 Identidade de Menon 
En 1965 P. Kesava Menon demostrou que



onde  é o número de divisores de .

 Funcións xeradoras 
A serie de Dirichlet para  pódese escribir en termos da función zeta de Riemann como: 



onde o lado esquerdo converxe para  .

A función xeradora da serie de Lambert é 



que converxe para .

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

Primeiro 



mais cando n vai ao infinito,  para todo 



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

 .

Tamén temos que 



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

Para a orde media, temos Sándor, Mitrinović & Crstici (2006) pp.24–25



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



(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 .

 Ratio de valores consecutivos 
En 1950 Somayajulu demostrou Ribenboim, p.38 Sándor, Mitrinović & Crstici (2006) p.16



En 1954 Schinzel e Sierpiński reforzaron isto, demostrando Ribenboim, p.38 Sándor, Mitrinović & Crstici (2006) p.16 que o conxunto



é denso nos números reais positivos. Tamén demostraron Ribenboim, p.38 que o conxunto



é 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.Guy (2004) p.144 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, Sándor & Crstici (2004) p.230 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  é



para unha constante . 

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



onde o termo de erro  é de orde como máximo .

 Aplicacións 

 Ciclotomía 
Na última sección das Disquisitiones Gauss, DA. The 7th § is arts. 336–366  Gauss demostra Gauss, DA, art 366 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 Gauss, DA, art. 366. This list is the last sentence in the Disquisitiones

 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. Ribenboim, pp. 36–37.

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 .Guy (2004) p.142

 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.Guy (2004) p.144

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



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

 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

Categoría:Teoría de números
Categoría:Álxebra
Categoría:Wikipedia:Páxinas con traducións non revisadas