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 n que son coprimos con n. 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 k no rango 1 ≤ k ≤ n para os que o máximo común divisor gcd(n, k) é igual a 1. [2] [3] Os números enteiros k desta forma denomínanse ás veces como totativos de n.
Por exemplo, os totativos de n = 9 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 gcd(9, 3) = gcd(9, 6) = 3 e gcd(9, 9) = 9. Polo tanto, φ(9) = 6. Un exempliño pequeno sería, φ(1) = 1 xa que para n = 1 o único enteiro no intervalo de 1 a n é o propio 1, e gcd(1, 1) = 1.
A función totiente de Euler é unha función multiplicativa, o que significa que se dous números m e n son coprimos, daquela φ(mn) = φ(m)φ(n).[4] [5] Esta función dá a orde do grupo multiplicativo de enteiros módulo n (o grupo de unidades do anel ).[6] Tamén se usa para definir o sistema de cifrado RSA.
Historia, terminoloxía e notación
editarLeonhard Euler introduciu a función en 1763. [7] [8] 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 πD para "a multitude de números inferiores a D, e que non teñen divisor común con ela". [9] A notación agora estándar [7] [10] φ(A) provén do tratado Disquisitiones Arithmeticae de Gauss de 1801,[11][12] aínda que Gauss non utilizou parénteses ao redor do argumento e escribiu φA. Así, a miúdo chámase función phi de Euler[13] ou simplemente función fi.
En 1879, J.J. Sylvester acuñou o termo "totient" para esta función, [14] polo que tamén se chama función totiente de Euler, totiente de Euler.
O cototiente de n defínese como . Conta o número de enteiros positivos inferiores ou iguais a n que teñen polo menos un factor primo en común con n.
Cálculo da función totiente de Euler
editarHai varias fórmulas para calcular φ(n) .
Fórmula do produto de Euler
editaronde o produto é sobre os distintos números primos que dividen n. (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
editarIsto significa que se gcd(m, n) = 1, daquela φ(m) φ(n) = φ(mn).
Esquema de demostración: Sexan A, B, C os conxuntos de enteiros positivos que son coprimos e inferiores a m, n, mn, respectivamente, de xeito que |A| = φ(m), etc. Entón hai unha bixección entre A × B e C polo teorema chinés do resto.
Valor de fi para un argumento que sexa potencia dun primo
editarSe p é primo e k ≥ 1, daquela
Proba da fórmula do produto de Euler
editarO teorema fundamental da aritmética estabelece que se n > 1 hai unha expresión única onde p1 < p2 < ... < pr son números primos e cada ki ≥ 1. (O caso n = 1 corresponde ao produto baleiro) Usando repetidamente a propiedade multiplicativa de φ e a fórmula para φ(pk) dá
Isto dá ambas as versións da fórmula do produto de Euler.
Exemplo
editarA fórmula alternativa usa só números enteiros,
Transformada de Fourier
editarO totiente é a transformada discreta de Fourier do mcd, avaliada en 1. [15] Sexa
onde xk = gcd(k,n) para k ∈ {1, ..., n}. 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 n. Porén, implica o cálculo do máximo común divisor de n e de cada número enteiro positivo menor que n, 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
editarA propiedade estabelecida por Gauss para os divisores d dun número n di[16]
- .
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 p e k ≥ 2. Esta fórmula tamén se pode derivar da fórmula do produto realizando ese produto para conseguir
Un exemplo:
Algúns valores
editarOs primeiros 100 valores (secuencia A000010 na OEIS) móstranse na táboa e no gráfico a continuación:
φ(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 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 y = n − 1 é un límite superior válido para tódolos n distintos de 1, e acadado se e só se n é un número primo. Un límite inferior simple é , que ten bastante marxe.
Teorema de Euler
editarO teorema de Euler indica que se a e n son primos relativos, daquela
O caso especial onde n é primo coñécese como pequeno teorema de Fermat.
Isto dedúcese do teorema de Lagrange e do feito de que φ(n) é a orde do grupo multiplicativo de enteiros módulo n.
Outras fórmulas
editar- En particular:
- Comparar isto coa fórmula (ver Mínimo común múltiplo).
- φ(n) é par para n ≥ 3. A maiores, se n ten r factores primos impares distintos, 2r | φ(n).
- Para todo a > 1 e n > 6 tal que 4 ∤ n existe un l ≥ 2n tal que l | φ(an − 1).
- . Onde rad(n) é o radical de n. (O produto de todos os números primos distintos que dividen n).
- ([17] citado en[18])
- [Liu (2016)]
- [17]
- ;[19]
- ;[19](onde γ é a constante de Euler–Mascheroni).
Identidade de Menon
editarEn 1965 P. Kesava Menon demostrou que
onde d(n) = σ0(n) é o número de divisores de n.
Funcións xeradoras
editarA serie de Dirichlet para φ(n) pódese escribir en termos da función zeta de Riemann como: [20]
onde o lado esquerdo converxe para .
A función xeradora da serie de Lambert é [21]
que converxe para |q| < 1.
Taxa de crecemento
editarSegundo as palabras de Hardy e Wright, a orde de φ(n) é "sempre case n".[22]
Primeiro [23]
mais cando n vai ao infinito, [24] para todo δ > 0
Estas dúas fórmulas pódense probar usando pouco máis que as fórmulas para φ(n) e a función suma de divisores σ(n) .
De feito, durante a proba da segunda fórmula, próbase a desigualdade
- .
Tamén temos que [25]
Aquí γ é a constante de Euler-Mascheroni, γ = 0.577215665... , polo que eγ = 1.7810724... e e−γ = 0.56145948... .
Para a orde media, temos [17][26]
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 "O grande" representa unha cantidade que está limitada por unha constante multiplicada pola función de n dentro dos parénteses (que é pequena en comparación con n2).
Este resultado pódese usar para demostrar [27] que a probabilidade de que dous números escollidos aleatoriamente sexan coprimos é 6/π2, que é a recíproca da zeta de Riemann de 2, igual a .
Ratio de valores consecutivos
editarEn 1950 Somayajulu demostrou [28] [29]
En 1954 Schinzel e Sierpiński reforzaron isto, demostrando [28] [29] que o conxunto
é denso nos números reais positivos. Tamén demostraron [28] que o conxunto
é denso no intervalo (0,1).
Números totientes
editarUn número totiente é un valor da función totiente de Euler: é dicir, un m para o cal hai polo menos un n para o cal φ(n) = m . A valencia ou multiplicidade dun número totiente m é o número de solucións desa ecuación.[30] 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, [31] e de feito cada número enteiro positivo ten un múltiplo que é un non totiente par. [32] O número de números totientes ata un límite dado x é
para unha constante C = 0.8178146.... [33]
Se se conta segundo a multiplicidade, o número de números totientes ata un determinado límite x é
onde o termo de erro R é de orde como máximo .
Aplicacións
editarCiclotomía
editarNa última sección das Disquisitiones [34] Gauss demostra [35] que un n-gono regular pode construírse con regra e compás se φ(n) é unha potencia de 2. Se n é 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 n é unha primeira potencia e n − 1 é 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 n-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 n son [36]
Teorema dos números primos para progresións aritméticas
editarO criptosistema RSA
editarConfigurar un sistema RSA implica escoller grandes números primos p e q, calcular n = pq e k = φ(n) e atopar dous números e e d tal que ed ≡ 1 (mod k). Os números n e e (a "chave de cifrado") son liberados ao público, e d (a "chave de descifrado") mantense en privado.
Unha mensaxe, representada por un número enteiro m, onde 0 < m < n, encriptase calculando S = me (mod n).
Descífrase calculando t = Sd (mod n). O teorema de Euler pódese usar para demostrar que se 0 < t < n, daquela t = m .
A seguridade dun sistema RSA veríase comprometida se o número n puidese factorizarse eficientemente ou se φ(n) puidese calcularse eficientemente sen factorizar n.
Problemas sen resolver
editarConxectura de Lehmer
editarSe p é primo, daquela φ(p) = p − 1. En 1932 D. H. Lehmer preguntou se hai números compostos n tal que φ(n) divide a n − 1. Non se coñece ningún. [37]
En 1933 demostrou que se existe algún n dese tipo, debe ser impar, libre de cadrados e divisíbel por polo menos sete números primos (é dicir, ω(n) ≥ 7 ). En 1980 Cohen e Hagis demostraron que n > 1020 e que ω(n) ≥ 14.[38] Alén diso, Hagis demostrou que se 3 divide n logo n > 101937042 e ω(n) ≥ 298848.[39][40]
A conxectura de Carmichael
editarDi que non hai un número n coa propiedade de que para todos os demais números m, m ≠ n, φ(m) ≠ φ(n).
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.[30]
Hipótese de Riemann
editarA hipótese de Riemann é certa se e só se a desigualdade
é certa para todos os n ≥ p120569# onde γ é a constante de Euler-Macheroni e p120569# é o produto dos primeiros 120569 primos.[41]
Notas
editar- ↑ "Euler's totient function". Khan Academy. Consultado o 2016-02-26.
- ↑ Long (1972)
- ↑ Pettofrezzo & Byrkit (1970)
- ↑ Long (1972)
- ↑ Pettofrezzo & Byrkit (1970)
- ↑ Ver Teorema de Euler.
- ↑ 7,0 7,1 Sandifer, p. 203
- ↑ Graham et al. p. 133 note 111
- ↑ 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).
- ↑ Both φ(n) and ϕ(n) are seen in the literature. These are two forms of the lower-case Greek letter phi.
- ↑ Gauss, Disquisitiones Arithmeticae article 38
- ↑ Cajori, Florian (1929). A History Of Mathematical Notations Volume II. Open Court Publishing Company. §409.
- ↑ Aí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
- ↑ 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.
- ↑ Schramm (2008)
- ↑ Gauss, DA, art 39
- ↑ 17,0 17,1 17,2 Walfisz, Arnold (1963). Weylsche Exponentialsummen in der neueren Zahlentheorie. Mathematische Forschungsberichte (en alemán) 16. Berlin: VEB Deutscher Verlag der Wissenschaften. Zbl 0146.06003.
- ↑ Lomadse, G. (1964). The scientific work of Arnold Walfisz (PDF). Acta Arithmetica 10. pp. 227–237. doi:10.4064/aa-10-3-227-237.
- ↑ 19,0 19,1 Sitaramachandrarao, R. (1985). "On an error term of Landau II". Rocky Mountain J. Math. 15 (2): 579–588. doi:10.1216/RMJ-1985-15-2-579.
- ↑ Hardy & Wright 1979
- ↑ Hardy & Wright 1979
- ↑ Hardy & Wright 1979
- ↑ Hardy & Wright 1979
- ↑ Hardy & Wright 1979
- ↑ Hardy & Wright 1979
- ↑ Sándor, Mitrinović & Crstici (2006) pp.24–25
- ↑ Hardy & Wright 1979
- ↑ 28,0 28,1 28,2 Ribenboim, p.38
- ↑ 29,0 29,1 Sándor, Mitrinović & Crstici (2006) p.16
- ↑ 30,0 30,1 Guy (2004) p.144
- ↑ Sándor & Crstici (2004) p.230
- ↑ Zhang, Mingzhi (1993). "On nontotients". Journal of Number Theory 43 (2): 168–172. ISSN 0022-314X. Zbl 0772.11001. doi:10.1006/jnth.1993.1014.
- ↑ Ford, Kevin (1998). "The distribution of totients". Ramanujan J. Developments in Mathematics 2 (1–2): 67–151. ISBN 978-1-4419-5058-1. ISSN 1382-4090. Zbl 0914.11053. arXiv:1104.3264. doi:10.1007/978-1-4757-4507-8_8.
- ↑ Gauss, DA. The 7th § is arts. 336–366
- ↑ Gauss, DA, art 366
- ↑ Gauss, DA, art. 366. This list is the last sentence in the Disquisitiones
- ↑ Ribenboim, pp. 36–37.
- ↑ Cohen, Graeme L.; Hagis, Peter Jr. (1980). "On the number of prime factors of n if φ(n) divides n − 1". Nieuw Arch. Wiskd. III Series 28: 177–185. ISSN 0028-9825. Zbl 0436.10002.
- ↑ Hagis, Peter Jr. (1988). "On the equation M·φ(n) = n − 1". Nieuw Arch. Wiskd. IV Series 6 (3): 255–261. ISSN 0028-9825. Zbl 0668.10006.
- ↑ Guy (2004) p.142
- ↑ Broughan, Kevin (2017). Equivalents of the Riemann Hypothesis, Volume One: Arithmetic Equivalents (First ed.). Cambridge University Press. ISBN 978-1-107-19704-6. Corollary 5.35
Véxase tamén
editarWikimedia Commons ten máis contidos multimedia na categoría: Función totiente de Euler |
Bibliografía
editar- Abramowitz, M.; Stegun, I. A. (1964). Handbook of Mathematical Functions. New York: Dover Publications. ISBN 0-486-61272-4.. See paragraph 24.3.2.
- Bach, Eric; Shallit, Jeffrey (1996). Algorithmic Number Theory (Vol I: Efficient Algorithms). MIT Press Series in the Foundations of Computing. Cambridge, MA: The MIT Press. ISBN 0-262-02405-5. Zbl 0873.11070.
- Dickson, Leonard Eugene, "History Of The Theory Of Numbers", vol 1, chapter 5 "Euler's Function, Generalizations; Farey Series", Chelsea Publishing 1952
- Ford, Kevin (1999). The number of solutions of φ(x) = m. Annals of Mathematics 150. pp. 283–311. ISSN 0003-486X. JSTOR 121103. MR 1715326. Zbl 0978.11053. doi:10.2307/121103..
- Gauss, Carl Friedrich (1986). Disquisitiones Arithmeticae (Second, corrected edition). Traducido por Clarke, Arthur A. New York: Springer. ISBN 0-387-96254-9.
- Gauss, Carl Friedrich (1965). Untersuchungen uber hohere Arithmetik (Disquisitiones Arithmeticae & other papers on number theory) (Second edition). Traducido por Maser, H. New York: Chelsea. ISBN 0-8284-0191-8.
- Graham, Ronald; Knuth, Donald; Patashnik, Oren (1994). Concrete Mathematics: a foundation for computer science (2nd ed.). Reading, MA: Addison-Wesley. ISBN 0-201-55802-5. Zbl 0836.00001.
- Guy, Richard K. (2004). Unsolved Problems in Number Theory. Problem Books in Mathematics (3rd ed.). New York, NY: Springer-Verlag. ISBN 0-387-20860-7. Zbl 1058.11001.
- Hardy, G. H.; Wright, E. M. (1979). An Introduction to the Theory of Numbers (Fifth ed.). Oxford: Oxford University Press. ISBN 978-0-19-853171-5.
- Liu, H.-Q. (2016). On Euler’s function. Proc. Roy. Soc. Edinburgh Sect. A 146..
- Long, Calvin T. (1972). Elementary Introduction to Number Theory (2nd ed.). Lexington: D. C. Heath and Company. LCCN 77-171950.
- Pettofrezzo, Anthony J.; Byrkit, Donald R. (1970). Elements of Number Theory. Englewood Cliffs: Prentice Hall. LCCN 77-81766.
- Ribenboim, Paulo (1996). The New Book of Prime Number Records (3rd ed.). New York: Springer. ISBN 0-387-94457-5. Zbl 0856.11001.
- Sandifer, Charles (2007). The early mathematics of Leonhard Euler. MAA. ISBN 978-0-88385-559-1.
- Sándor, József; Mitrinović, Dragoslav S.; Crstici, Borislav, eds. (2006). Handbook of number theory I. Dordrecht: Springer-Verlag. pp. 9–36. ISBN 1-4020-4215-9. Zbl 1151.11300.
- Sándor, Jozsef; Crstici, Borislav (2004). Handbook of number theory II. Dordrecht: Kluwer Academic. pp. 179–327. ISBN 1-4020-2546-7. Zbl 1079.11001.
- Schramm, Wolfgang (2008). The Fourier transform of functions of the greatest common divisor. Electronic Journal of Combinatorial Number Theory A50..
Outros artigos
editar- 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
editar- "Totient function". Encyclopedia of Mathematics. EMS Press. 2001 [1994].
- Euler's Phi Function and the Chinese Remainder Theorem — proof that φ(n) is multiplicative Arquivado 2021-02-28 en Wayback Machine.
- Euler's totient function calculator in JavaScript — up to 20 digits
- Dineva, Rosica, The Euler Totient, the Möbius, and the Divisor Functions Arquivado 2021-01-16 en Wayback Machine.
- Plytage, Loomis, Polhill Summing Up The Euler Phi Function