Función totiente de Euler

Os primeiros mil valores de Modelo:Math. Os puntos da liña superior representan Modelo:Math cando Modelo:Mvar é un número primo, que é Modelo:Math

En teoría de números, a función totiente de Euler conta os enteiros positivos ata un número enteiro dado Modelo:Mvar que son coprimos con Modelo:Mvar. Escríbese usando a letra grega fi como $\phi (n)$ ou $\varphi (n)$, e tamén se pode chamar función fi de Euler. Noutras palabras, é o número de enteiros Modelo:Mvar no rango Modelo:Math para os que o máximo común divisor Modelo:Math é igual a 1. Os números enteiros Modelo:Mvar desta forma denomínanse ás veces como totativos de Modelo:Mvar.

Por exemplo, os totativos de Modelo:Math 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 Modelo:Math e Modelo:Math. Polo tanto, Modelo:Math. Un exempliño pequeno sería, Modelo:Math xa que para Modelo:Math o único enteiro no intervalo de 1 a Modelo:Mvar é o propio 1, e Modelo:Math.

A función totiente de Euler é unha función multiplicativa, o que significa que se dous números Modelo:Mvar e Modelo:Mvar son coprimos, daquela Modelo:Math. Esta función dá a orde do [[Grupo multiplicativo de números enteiros módulo n|grupo multiplicativo de enteiros módulo Modelo:Mvar]] (o grupo de unidades do anel $\mathbb{Z}/n\mathbb{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 Modelo:Mvar para denotala: escribiu Modelo:Math para "a multitude de números inferiores a Modelo:Mvar, e que non teñen divisor común con ela". A notación agora estándar Modelo:Math provén do tratado Disquisitiones Arithmeticae de Gauss de 1801, aínda que Gauss non utilizou parénteses ao redor do argumento e escribiu Modelo:Math. 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 Modelo:Mvar defínese como $n-\phi (n)$. Conta o número de enteiros positivos inferiores ou iguais a Modelo:Mvar que teñen polo menos un factor primo en común con Modelo:Mvar.

Cálculo da función totiente de Euler

Hai varias fórmulas para calcular Modelo:Math .

Fórmula do produto de Euler

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

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

Unha formulación equivalente é $\phi (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,\dots ,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 Modelo:Math, daquela Modelo:Math.

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

Valor de fi para un argumento que sexa potencia dun primo

Se Modelo:Mvar é primo e Modelo:Math, daquela

$\phi \left(p^k\right)=p^k-p^{k-1}=p^{k-1}(p-1)=p^k(1-\frac{1}{p}).$

Proba da fórmula do produto de Euler

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

$\begin{array}{ccc}\phi (n)& =& \phi (p_1^{k_1})\phi (p_2^{k_2})\cdots \phi (p_r^{k_r})\\ & =& p_1^{k_1}(1-\frac{1}{p_1})p_2^{k_2}(1-\frac{1}{p_2})\cdots p_r^{k_r}(1-\frac{1}{p_r})\\ & =& p_1^{k_1}{p}_2^{k_2}\cdots p_r^{k_r}(1-\frac{1}{p_1})(1-\frac{1}{p_2})\cdots (1-\frac{1}{p_r})\\ & =& n(1-\frac{1}{p_1})(1-\frac{1}{p_2})\cdots (1-\frac{1}{p_r}).\end{array}$

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

Exemplo

$\phi (20)=\phi (2^{2}5)=20(1-\frac{1}{2})(1-\frac{1}{5})=20\cdot \frac{1}{2}\cdot \frac{4}{5}=8.$

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

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

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

onde Modelo:Math para Modelo:Math. Daquela

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

A parte real desta fórmula é

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

Por exemplo, usando $\cos \frac{\pi }{5}=\frac{\sqrt{5}+1}{4}$ e $\cos \frac{2\pi }{5}=\frac{\sqrt{5}-1}{4}$ : $$\begin{array}{ccc}\phi (10)& =& \gcd (1,10)\cos \frac{2\pi }{10}+\gcd (2,10)\cos \frac{4\pi }{10}+\gcd (3,10)\cos \frac{6\pi }{10}+\cdots +\gcd (10,10)\cos \frac{20\pi }{10}\\ & =& 1\cdot (\frac{\sqrt{5}+1}{4})+2\cdot (\frac{\sqrt{5}-1}{4})+1\cdot (-\frac{\sqrt{5}-1}{4})+2\cdot (-\frac{\sqrt{5}+1}{4})+5\cdot (-1)\\ & & +2\cdot (-\frac{\sqrt{5}+1}{4})+1\cdot (-\frac{\sqrt{5}-1}{4})+2\cdot (\frac{\sqrt{5}-1}{4})+1\cdot (\frac{\sqrt{5}+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 Modelo:Mvar. Porén, implica o cálculo do máximo común divisor de Modelo:Mvar e de cada número enteiro positivo menor que Modelo:Mvar, 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 Modelo:Mvar dun número Modelo:Mvar di

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

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

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

onde Modelo:Mvar é a función de Möbius, función multiplicativa definida por $\mu (p)=-1$ e $\mu (p^k)=0$ para cada primo Modelo:Math e Modelo:Math. 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{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}$

Algúns valores

Os primeiros 100 valores Modelo:OEIS móstranse na táboa e no gráfico a continuación:

Gráfico dos 100 primeiros valores

Modelo:Math para Modelo:Math

+	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 Modelo:Math é un límite superior válido para tódolos Modelo:Mvar distintos de 1, e acadado se e só se Modelo:Mvar é un número primo. Un límite inferior simple é $\phi (n)\ge \sqrt{n/2}$, que ten bastante marxe.

Teorema de Euler

O teorema de Euler indica que se Modelo:Mvar e Modelo:Mvar son primos relativos, daquela

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

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

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

Outras fórmulas

• $a\mid b⟹\phi (a)\mid \phi (b)$
• $m\mid \phi (a^m-1)$
• $\phi (mn)=\phi (m)\phi (n)\cdot \frac{d}{\phi (d)}\text{onde }d=\gcd (m,n)$ En particular:
  • $\phi (2m)=\{\begin{array}{cc}2\phi (m)& \text{ if }m\text{ é par}\\ \phi (m)& \text{ if }m\text{ é impar}\end{array}$
  • $\phi \left(n^m\right)=n^{m-1}\phi (n)$
• $\phi (\mathrm{lcm}(m,n))\cdot \phi (\gcd (m,n))=\phi (m)\cdot \phi (n)$ Comparar isto coa fórmula $\mathrm{lcm}(m,n)\cdot \gcd (m,n)=m\cdot n$ (ver Mínimo común múltiplo).
• Modelo:Math é par para Modelo:Math. A maiores, se Modelo:Mvar ten Modelo:Mvar factores primos impares distintos, Modelo:Math.
• Para todo Modelo:Math e Modelo:Math tal que Modelo:Math existe un Modelo:Math tal que Modelo:Math.
• $\frac{\phi (n)}{n}=\frac{\phi (\mathrm{rad}(n))}{\mathrm{rad}(n)}$. Onde Modelo:Math é o radical de Modelo:Mvar. (O produto de todos os números primos distintos que dividen Modelo:Mvar).
• $\sum _{d\mid n}\frac{{\mu }^2(d)}{\phi (d)}=\frac{n}{\phi (n)}$
• $\sum _{\genfrac{}{}{0ex}{}{1\le k\le n-1}{gcd(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\phi (k)=\frac{3}{{\pi }^2}{n}^2+O(n(\log n{)}^{\frac{2}{3}}(\log \log n{)}^{\frac{1}{3}})$ [Liu (2016)]
• $\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{ prime}}\frac{\log p}{p^2-p+1})+O\left(\frac{(\log n{)}^{\frac{2}{3}}}{n}\right)$;(onde Modelo:Mvar é a constante de Euler–Mascheroni).

Identidade de Menon

En 1965 P. Kesava Menon demostrou que

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

onde Modelo:Math é o número de divisores de Modelo:Mvar.

Funcións xeradoras

A serie de Dirichlet para Modelo:Math pódese escribir en termos da función zeta de Riemann como:

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

onde o lado esquerdo converxe para $\mathrm{\Re }(s)>2$ .

A función xeradora da serie de Lambert é

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

que converxe para Modelo:Math.

Taxa de crecemento

Segundo as palabras de Hardy e Wright, a orde de Modelo:Math é "sempre case Modelo:Mvar".

Primeiro

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

mais cando n vai ao infinito, para todo Modelo:Math

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

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

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

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

Tamén temos que

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

Aquí Modelo:Mvar é a constante de Euler-Mascheroni, Modelo:Math , polo que Modelo:Math e Modelo:Math .

Para a orde media, temos

$\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{cando }n\to \mathrm{\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(n(\log n{)}^{\frac{2}{3}}(\log \log n{)}^{\frac{1}{3}})$

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

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

Ratio de valores consecutivos

En 1950 Somayajulu demostrou

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

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

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

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

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

é denso no intervalo (0,1).

Números totientes

Un número totiente é un valor da función totiente de Euler: é dicir, un Modelo:Mvar para o cal hai polo menos un Modelo:Mvar para o cal Modelo:Math . A valencia ou multiplicidade dun número totiente Modelo:Mvar é 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 Modelo:Mvar é

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

para unha constante Modelo:Math.

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

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

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

Aplicacións

Ciclotomía

Na última sección das Disquisitiones Gauss demostra que un Modelo:Mvar-gono regular pode construírse con regra e compás se Modelo:Math é unha potencia de 2. Se Modelo:Mvar é 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 Modelo:Mvar é unha primeira potencia e Modelo:Math é 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 Modelo:Mvar-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 Modelo:Mvar son

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

O criptosistema RSA

Configurar un sistema RSA implica escoller grandes números primos Modelo:Mvar e Modelo:Mvar, calcular Modelo:Math e Modelo:Math e atopar dous números Modelo:Mvar e Modelo:Mvar tal que Modelo:Math. Os números Modelo:Mvar e Modelo:Mvar (a "chave de cifrado") son liberados ao público, e Modelo:Mvar (a "chave de descifrado") mantense en privado.

Unha mensaxe, representada por un número enteiro Modelo:Mvar, onde Modelo:Math, encriptase calculando Modelo:Math.

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

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

Problemas sen resolver

Conxectura de Lehmer

Se Modelo:Mvar é primo, daquela Modelo:Math. En 1932 D. H. Lehmer preguntou se hai números compostos Modelo:Mvar tal que Modelo:Math divide a Modelo:Math. Non se coñece ningún.

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

A conxectura de Carmichael

Di que non hai un número Modelo:Mvar coa propiedade de que para todos os demais números Modelo:Mvar, Modelo:Math, Modelo:Math.

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}{\phi (n)}<e^{\gamma }\log \log n+\frac{e^{\gamma }(4+\gamma -\log 4\pi )}{\sqrt{\log n}}$

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

Véxase tamén

Bibliografía

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

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

• Modelo:Springer
• Euler's Phi Function and the Chinese Remainder Theorem — proof that Modelo:Math is multiplicative Modelo:Webarchive
• Euler's totient function calculator in JavaScript — up to 20 digits
• Dineva, Rosica, The Euler Totient, the Möbius, and the Divisor Functions Modelo:Webarchive
• Plytage, Loomis, Polhill Summing Up The Euler Phi Function