TotientFunction

A função totiente phi(n), também denominada função totiente de Euler, é definida com o número de inteiros positivos <=n que são relativamente primos (ou seja, não contém nenhum factor em comum com) n, onde 1 é contado como sendo relativamente privilegiado para todos os números. Uma vez que um número inferior ou igual a relativamente primos de um número é chamado um totative, a função totiente phi(n) pode ser simplesmente definido com o número de totatives de  n. Por exemplo, existem oito totatives de 24 (1, 5, 7, 11, 13, 17, 19, e 23), então phi(24)=8. A função totiente é implementada na Matemática como Euler Phi [n].

phi(n) é sempre o mesmo para n>=3. Por convenção, phi(0)=1, embora a Matemática defina Euler Phi[0] igual a 0 a coerência com o seu comando Integer Factor [0]. Os primeiros valores de phi(n) para n=1, 2, ... são 1, 1, 2, 2, 4, 2, 6, 4, 6, 4, 10, ... (Sloane's A000010). A função totiente é dada pela transformação de Moebius 1, 2, 3, 4, ... (Sloane e Plouffe). phi(n) é plotado acima para pequenas n.

Para um primo p,

 phi(p)=p-1,

(1)

Uma vez que todos os números inferiores p são relativamente primos a p. Se m=p^alpha é uma potência de um primo, então os números que têm um factor comum com m são os múltiplos de  p: p, 2p, ..., (p^(alpha-1))p. Tem p^(alpha-1) desses múltiplos, de modo que o número de factores relativamente privilegiado com p^alphaé

phi(p^alpha)

=

p^alpha-p^(alpha-1)

(2)

=

p^(alpha-1)(p-1)

(3)

=

p^alpha(1-1/p).

(4)

Agora, dê uma geral m divisível por p. Deixe phi_p(m) ser o número de números inteiros positivos <=m não divisível por p. Como anteriormente, p, 2p, ..., (m/p)p  têm factores comuns, de modo

phi_p(m)

=

m-m/p

(5)

=

m(1-1/p).

(6)

Agora vamos q ser outro primo dividindo m. Os inteiros divisíveis por q  sãoq, 2q, ..., (m/q)q. Mas estes duplicam pq, 2pq, ..., (m/(pq))pq. Portanto, o número de termos que deve ser subtraído de obter é

Deltaphi_q(m)

=

m/q-m/(pq)

(7)

=

m/q(1-1/p),

(8)

e

phi_(pq)(m)

=

phi_p(m)-Deltaphi_q(m)

(9)

=

m(1-1/p)-m/q(1-1/p)

(10)

=

m(1-1/p)(1-1/q).

(11)

Por indução, o caso geral é então

phi(n)

=

nproduct_(p|n)(1-1/p)

(12)

=

n(1-1/(p_1))(1-1/(p_2))...(1-1/(p_r)),

(13)

Onde, o produto é executado sobre todos os números primos p dividindo n. Uma identidade interresante relativa phi(n^k) para phi(n) é dado por

 phi(n^k)=n^(k-1)phi(n)

(14)

(A. Olofsson).

Outra identidade relaciona os divisores  d de n para n via

 sum_(d|n)phi(d)=n.

(15)

A função totiente está ligada à função de Moebius mu(n) através da soma

 sum_(d)dmu(n/d)=phi(n),

(16)

Onde a soma é maior que os divisores n, o que pode ser provado por indução em n e o facto mu(n) e phi(n) são multiplicativos (Berlekamp; van Lint and Nienhuys).

A função totiente tem a função de gerar séries de Dirichlet

 sum_(n=1)^infty(phi(n))/(n^s)=(zeta(s-1))/(zeta(s))

(17)

para s>2 (Hardy and Wright).

A função totiente satisfaz a desigualdade

 phi(n)>=sqrt(n)

(18)

Para todos n excepto n=2 e n=6 (Kendall and Osborn 1965; Mitrinović e Sándor 1995, p. 9). Assim, os únicos valores de n para os quais phi(n)=2 sãon=3, 4, e 6. Além disso, para o composto n,

 phi(n)<=n-sqrt(n)

(19)

(Sierpiński e Schinzel 1988; Mitrinović e Sándor).

TotientFunctionInequality

phi(n) também satisfaz

 lim inf_(n->infty)phi(n)(lnlnn)/n=e^(-gamma),

(20)

onde gamma é a característica constante de Euler-Mascheroni. Os valores de n para os quais phi(n)<e^(-gamma)n/(lnlnn) são dados por 3, 4, 5, 6, 8, 9, 10, 12, 14, 15, 16, 18, 20, 22, ... (Sloane's A100966).

A função de divisor satisfaz a congruência

nsigma(n)

=

2 (mod phi(n))

(21)

=

{0 (mod phi(n)) if phi(n)=2; 2 (mod phi(n)) otherwise

(22)

Para todos os números primos p>=5 e nenhum composto com a excepção de 4, 6, e 22, onde sigma(n) é a função de divisor. Este facto foi provado por Subbarao, apesar da implicação em contrário, "é verdade para infinitamente muitos compósitos n?," afirmou em Guy, uma consulta posteriormente removida por Guy. Nenhuma solução é composta actualmente conhecida por

 n-1=0 (mod phi(n))

(23)

(Honsberger).

Um corolário do teorema Zsigmondy leva à seguinte congruência,

 phi(a^n+b^n)=0 (mod n)

(24)

(Zsigmondy, Moree, Ruiz).

Os primeiros n para os quais

 phi(n)=phi(n+1)

(25)

São dados por 1, 3, 15, 104, 164, 194, 255, 495, 584, 975, ... (Sloane's A001274), que têm valores comuns phi(n)=1, 2, 8, 48, 80, 96, 128, 240, 288, 480, ... (Sloane's A003275).

A única n<10^(10) para os quais

 phi(n)=phi(n+1)=phi(n+2)

(26)

é n=5186, dando

 phi(5186)=phi(5187)=phi(5188)=2^53^4

(27)

(Guy).

Valores de phi(n) compartilhado entre n que estão juntos incluem

phi(25930)

=

phi(25935)=phi(25940)=phi(25942)

(28)

=

2^73^4

(29)

phi(404471)

=

phi(404473)=phi(404477)

(30)

=

2^83^25^27

(31)

(Guy). McCranie encontrou uma progressão aritmética de seis números com funções Totiente iguais,

 phi(583200)=phi(583230)=phi(583260)=phi(583290) 
 =phi(583320)=phi(583350)=155520,

(32)

Bem como outras progressões de seis números começando 1166400, 1749600, ... (Sloane's A050518).

Se a conjectura de Goldbach é verdadeira, então, para cada inteiro positivo m, existem primos p e q de tal modo que

 phi(p)+phi(q)=2m

(33)

(Guy). Erdős perguntou se isso vale para p e q não necessariamente privilegiada, mas esta forma descontraída ainda não foi provada(Guy).

Guy discutiu soluções para

 phi(sigma(n))=n,

(34)

onde sigma(n) é a função de divisor. F. Helenius encontrou 365 tais soluções, e a primeira das quais está 2, 8, 12, 128, 240, 720, 6912, 32768, 142560, 712800, ... (Sloane's A001229).