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 ${\displaystyle \varphi (n)}$ ou ${\displaystyle \phi (n)}$, 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.

Os primeiros mil valores de φ(n). Os puntos da liña superior representan φ(p) cando p é un número primo, que é p − 1.^[1]

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 ${\displaystyle \mathbb {Z} /n\mathbb {Z} }$).^[6] 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. ^{[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 ${\displaystyle n-\varphi (n)}$. 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

Hai varias fórmulas para calcular φ(n) .

Fórmula do produto de Euler

${\displaystyle \varphi (n)=n\prod _{p\mid n}\left(1-{\frac {1}{p}}\right),}$

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

Unha formulación equivalente é ${\displaystyle \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 ${\displaystyle n=p_{1}^{k_{1}}p_{2}^{k_{2}}\cdots p_{r}^{k_{r}}}$ é a descomposición en factores primos de ${\displaystyle n}$ (é dicir, ${\displaystyle 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 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

Se p é primo e k ≥ 1, daquela

${\displaystyle \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 n > 1 hai unha expresión única ${\displaystyle n=p_{1}^{k_{1}}p_{2}^{k_{2}}\cdots p_{r}^{k_{r}},}$ onde p₁ < p₂ < ... < p_r son números primos e cada k_i ≥ 1. (O caso n = 1 corresponde ao produto baleiro) Usando repetidamente a propiedade multiplicativa de φ e a fórmula para φ(p^k) dá

${\displaystyle {\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

${\displaystyle \varphi (20)=\varphi (2^{2}5)=20\,(1-{\tfrac {1}{2}})\,(1-{\tfrac {1}{5}})=20\cdot {\tfrac {1}{2}}\cdot {\tfrac {4}{5}}=8.}$

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

${\displaystyle \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. ^[15] Sexa

${\displaystyle {\mathcal {F}}\{\mathbf {x} \}[m]=\sum \limits _{k=1}^{n}x_{k}\cdot e^{{-2\pi i}{\frac {mk}{n}}}}$

onde x_k = gcd(k,n) para k ∈ {1, ..., n}. Daquela

${\displaystyle \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 é

${\displaystyle \varphi (n)=\sum \limits _{k=1}^{n}\gcd(k,n)\cos {\tfrac {2\pi k}{n}}.}$

Por exemplo, usando ${\displaystyle \cos {\tfrac {\pi }{5}}={\tfrac {{\sqrt {5}}+1}{4}}}$ e ${\displaystyle \cos {\tfrac {2\pi }{5}}={\tfrac {{\sqrt {5}}-1}{4}}}$ : $${\displaystyle {\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 {{\sqrt {5}}+1}{4}})+2\cdot ({\tfrac {{\sqrt {5}}-1}{4}})+1\cdot (-{\tfrac {{\sqrt {5}}-1}{4}})+2\cdot (-{\tfrac {{\sqrt {5}}+1}{4}})+5\cdot (-1)\\&&+\ 2\cdot (-{\tfrac {{\sqrt {5}}+1}{4}})+1\cdot (-{\tfrac {{\sqrt {5}}-1}{4}})+2\cdot ({\tfrac {{\sqrt {5}}-1}{4}})+1\cdot ({\tfrac {{\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 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

A propiedade estabelecida por Gauss para os divisores d dun número n di^[16]

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

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

${\displaystyle \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 ${\displaystyle \mu (p)=-1}$ e ${\displaystyle \mu (p^{k})=0}$ para cada primo p e k ≥ 2. Esta fórmula tamén se pode derivar da fórmula do produto realizando ese produto ${\textstyle \prod _{p\mid n}(1-{\frac {1}{p}})}$ para conseguir ${\textstyle \sum _{d\mid n}{\frac {\mu (d)}{d}}.}$

Un exemplo:

${\displaystyle {\begin{aligned}\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{aligned}}}$

Algúns valores

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

Gráfico dos 100 primeiros valores

φ(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 é ${\displaystyle \varphi (n)\geq {\sqrt {n/2}}}$, que ten bastante marxe.

Teorema de Euler

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

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

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

• ${\displaystyle a\mid b\implies \varphi (a)\mid \varphi (b)}$
• ${\displaystyle m\mid \varphi (a^{m}-1)}$
• ${\displaystyle \varphi (mn)=\varphi (m)\varphi (n)\cdot {\frac {d}{\varphi (d)}}\quad {\text{onde }}d=\operatorname {gcd} (m,n)}$ En particular:
  • ${\displaystyle \varphi (2m)={\begin{cases}2\varphi (m)&{\text{ if }}m{\text{ é par}}\\\varphi (m)&{\text{ if }}m{\text{ é impar}}\end{cases}}}$
  • ${\displaystyle \varphi \left(n^{m}\right)=n^{m-1}\varphi (n)}$
• ${\displaystyle \varphi (\operatorname {lcm} (m,n))\cdot \varphi (\operatorname {gcd} (m,n))=\varphi (m)\cdot \varphi (n)}$ Comparar isto coa fórmula ${\textstyle \operatorname {lcm} (m,n)\cdot \operatorname {gcd} (m,n)=m\cdot n}$ (ver Mínimo común múltiplo).
• φ(n) é par para n ≥ 3. A maiores, se n ten r factores primos impares distintos, 2^r | φ(n).
• Para todo a > 1 e n > 6 tal que 4 ∤ n existe un l ≥ 2n tal que l | φ(aⁿ − 1).
• ${\displaystyle {\frac {\varphi (n)}{n}}={\frac {\varphi (\operatorname {rad} (n))}{\operatorname {rad} (n)}}}$. Onde rad(n) é o radical de n. (O produto de todos os números primos distintos que dividen n).
• ${\displaystyle \sum _{d\mid n}{\frac {\mu ^{2}(d)}{\varphi (d)}}={\frac {n}{\varphi (n)}}}$
• ${\displaystyle \sum _{1\leq k\leq n-1 \atop gcd(k,n)=1}\!\!k={\tfrac {1}{2}}n\varphi (n)\quad {\text{para }}n>1}$
• ${\displaystyle \sum _{k=1}^{n}\varphi (k)={\tfrac {1}{2}}\left(1+\sum _{k=1}^{n}\mu (k)\left\lfloor {\frac {n}{k}}\right\rfloor ^{2}\right)={\frac {3}{\pi ^{2}}}n^{2}+O\left(n(\log n)^{\frac {2}{3}}(\log \log n)^{\frac {4}{3}}\right)}$(^[17] citado en^[18])
• ${\displaystyle \sum _{k=1}^{n}\varphi (k)={\frac {3}{\pi ^{2}}}n^{2}+O\left(n(\log n)^{\frac {2}{3}}(\log \log n)^{\frac {1}{3}}\right)}$ [Liu (2016)]
• ${\displaystyle \sum _{k=1}^{n}{\frac {\varphi (k)}{k}}=\sum _{k=1}^{n}{\frac {\mu (k)}{k}}\left\lfloor {\frac {n}{k}}\right\rfloor ={\frac {6}{\pi ^{2}}}n+O\left((\log n)^{\frac {2}{3}}(\log \log n)^{\frac {4}{3}}\right)}$ ^[17]
• ${\displaystyle \sum _{k=1}^{n}{\frac {k}{\varphi (k)}}={\frac {315\,\zeta (3)}{2\pi ^{4}}}n-{\frac {\log n}{2}}+O\left((\log n)^{\frac {2}{3}}\right)}$;^[19]
• ${\displaystyle \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)^{\frac {2}{3}}}{n}}\right)}$;^[19](onde γ é a constante de Euler–Mascheroni).

Identidade de Menon

En 1965 P. Kesava Menon demostrou que

${\displaystyle \sum _{\stackrel {1\leq k\leq n}{\gcd(k,n)=1}}\!\!\!\!\gcd(k-1,n)=\varphi (n)d(n),}$

onde d(n) = σ₀(n) é o número de divisores de n.

Funcións xeradoras

A serie de Dirichlet para φ(n) pódese escribir en termos da función zeta de Riemann como: ^[20]

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

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

A función xeradora da serie de Lambert é ^[21]

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

que converxe para |q| < 1.

Taxa de crecemento

Segundo as palabras de Hardy e Wright, a orde de φ(n) é "sempre case n".^[22]

Primeiro ^[23]

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

mais cando n vai ao infinito, ^[24] para todo δ > 0

${\displaystyle {\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 φ(n) e a función suma de divisores σ(n) .

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

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

Tamén temos que ^[25]

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

Aquí γ é a constante de Euler-Mascheroni, γ = 0.577215665... , polo que e^γ = 1.7810724... e e^−γ = 0.56145948... .

Para a orde media, temos ^[17][26]

${\displaystyle \varphi (1)+\varphi (2)+\cdots +\varphi (n)={\frac {3n^{2}}{\pi ^{2}}}+O\left(n(\log n)^{\frac {2}{3}}(\log \log n)^{\frac {4}{3}}\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

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

(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 n²).

Este resultado pódese usar para demostrar ^[27] que a probabilidade de que dous números escollidos aleatoriamente sexan coprimos é 6/π², que é a recíproca da zeta de Riemann de 2, igual a ${\displaystyle 1/\zeta (2)}$.

Ratio de valores consecutivos

En 1950 Somayajulu demostrou ^{[28] [29]}

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

En 1954 Schinzel e Sierpiński reforzaron isto, demostrando ^{[28] [29]} que o conxunto

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

é denso nos números reais positivos. Tamén demostraron ^[28] que o conxunto

${\displaystyle \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 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 é

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

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 é

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

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

Aplicacións

Ciclotomía

Na ú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]

2, 3, 4, 5, 6, 8, 10, 12, 15, 16, 17, 20, 24, 30, 32, 34, 40,... (secuencia A003401 na OEIS) .

Teorema dos números primos para progresións aritméticas

O criptosistema RSA

Configurar 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 = m^e (mod n).

Descífrase calculando t = S^d (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

Conxectura de Lehmer

Se 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 > 10²⁰ e que ω(n) ≥ 14.^[38] Alén diso, Hagis demostrou que se 3 divide n logo n > 10^1937042 e ω(n) ≥ 298848.^[39][40]

A conxectura de Carmichael

Di 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

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

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

é certa para todos os n ≥ p₁₂₀₅₆₉# onde γ é a constante de Euler-Macheroni e p₁₂₀₅₆₉# é o produto dos primeiros 120569 primos.^[41]