TotientFunction

La funzione totiente phi(n), chiamata anche funzione totiente di Eulero, è definita, per ogni intero positivo <=n che sono coprimi con (cioè non contengono nessun fattore in comune) n, dove 1 è contato come coprimo verso tutti i numeri. Poichè un numero minore/uguale e coprimo a un numero dato è chiamato totative, la funzione totiente phi(n) può essere definita semplicemente come il numero di totatives di n. Per esempio, ci sono otto totatives di 24 (1, 5, 7, 11, 13, 17, 19, e 23), quindi phi(24)=8. La funzione totiente è implementata in Mathematica come EulerPhi[n].

phi(n) è sempre pari per n>=3. Per convenzione, phi(0)=1, sebbene Mathematica definisce EulerPhi[0] uguale a 0 per coerenza con il suo comando FactorInteger[0]. I primi valori di phi(n) per n=1, 2, ... sono 1, 1, 2, 2, 4, 2, 6, 4, 6, 4, 10, ... (Sloane's A000010). La funzione totiente è ottenuta dalla trasformazione di Möbius di 1, 2, 3, 4, ... (Sloane e Plouffe 1995, p. 22). phi(n) è riportato sopre per le piccole n.

Per il primo p,

 phi(p)=p-1,
(1)

poichè tutti i numeri sono minori di p sono coprimi a p. Se m=p^alpha è una potenza di un numero primo, quindi i numeri che hanno un fattore comune con m sono multipli di p: p, 2p, ..., (p^(alpha-1))p. Ci sono p^(alpha-1) di questi multipli, così il numero di fattori coprimi a p^alpha è

phi(p^alpha)=p^alpha-p^(alpha-1)
(2)
=p^(alpha-1)(p-1)
(3)
=p^alpha(1-1/p).
(4)

Ora prendiamo un generico m divisible per p. Sia phi_p(m) il numero di interi positivi <=m non divisibile per p. Come prima, p, 2p, ..., (m/p)p ha fattori comuni, quindi

phi_p(m)=m-m/p
(5)
=m(1-1/p).
(6)

Ora sia q un altro dividendo primo m. Gli interi divisibili per q sono q, 2q, ..., (m/q)q. Ma questi duplicati pq, 2pq, ..., (m/(pq))pq. So the numero di termini che devono essere sottratti phi_p per ottenere phi_(pq) è

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)

Per induzione, il caso generale è

phi(n)=nproduct_(p|n)(1-1/p)
(12)
=n(1-1/(p_1))(1-1/(p_2))...(1-1/(p_r)),
(13)

dove il prodotto viene eseguito su tutti i primi p dividing n. Un'identità interessante relativa a phi(n^k) to phi(n) è data da

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

(A. Olofsson, pers. comm., Dec. 30, 2004).

Un'altra identità riguarda i divisori d da n a n via

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

La funzione totiente è collegata alla funzione di Möbius mu(n) attraverso la somma

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

dove la somma supera i divisori di n, che può essere dimostrato per induzione su n e il fatto che mu(n) e phi(n) sono moltiplicativi (Berlekamp 1968, pp. 91-93; van Lint and Nienhuys 1991, p. 123).

La funzione totiente ha come funzione generatrice la serie di Dirichlet

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

per s>2 (Hardy e Wright 1979, p. 250).

La funzione totiente soddisfa la disuguaglianza

 phi(n)>=sqrt(n)
(18)

per ogni n tranne n=2 e n=6 (Kendall e Osborn 1965; Mitrinović e Sándor 1995, p. 9). Pertanto, gli unici valori di n per cui phi(n)=2 sono n=3, 4, e 6. Inoltre, per composizione di n,

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

(Sierpiński and Schinzel 1988; Mitrinović and Sándor 1995, p. 9).

TotientFunctionInequality

phi(n) soddisfa anche

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

dove gamma è la costante di Eulero-Mascheroni. I valori di n per cui phi(n)<e^(-gamma)n/(lnlnn) sono ottenuti da 3, 4, 5, 6, 8, 9, 10, 12, 14, 15, 16, 18, 20, 22, ... (Sloane's A100966).

La funzione divisore soddisfa la congruenza

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

per tutti i primi p>=5 e non composito con l' eccezione di 4, 6, e 22, dove sigma(n) è la funzione divisore. Questo fatto è stato dimostrato da Subbarao (1974), nonostante la implicazioni contrarie, "is it true for infinitely many composite n?," indicato in Guy (1994, p. 92), una query successivamente rimossa da Guy (2004, p. 142). Nessuna soluzione composita è attualmente nota

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

(Honsberger 1976, p. 35).

Un corollario del teorema di Zsigmondy conduce alla seguente congruenza,

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

(Zsigmondy 1882, Moree 2004, Ruiz 2004ab).

Le prime n per cui

 phi(n)=phi(n+1)
(25)

sono date da 1, 3, 15, 104, 164, 194, 255, 495, 584, 975, ... (Sloane's A001274), che hanno valori comuni phi(n)=1, 2, 8, 48, 80, 96, 128, 240, 288, 480, ... (Sloane's A003275).

La sola n<10^(10) per cui

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

è n=5186, ottenendo

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

(Guy 2004, p. 139).

I valori di phi(n) condivisi attraverso n that are close together include

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 2004, p. 139). McCranie ha trovato una progressione aritmetica di sei numeri con funzioni totiente uguali,

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

così come altre progressioni di sei numeri a partire da 1166400, 1749600, ... (Sloane's A050518).

Se la congettura di Goldbach è vera, allora per ogni intero positivo m, ci sono primi p e q tali che

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

(Guy 2004, p. 160). Erdős chiese se questo valeva per p e q non necessariamente primo, ma questa forma rilassata rimane senza dimostrazione (Guy 2004, p. 160).

Guy (2004, p. 150) ha discusso le soluzioni di

 phi(sigma(n))=n,
(34)

dove sigma(n) è la funzione divisiore. F. Helenius ha trovato 365 solutioni, le prime delle quali sono 2, 8, 12, 128, 240, 720, 6912, 32768, 142560, 712800, ... (Sloane's A001229).