Totient Function

Author

Eric W. Weisstein
September 3, 2008

This notebook downloaded from http://mathworld.wolfram.com/notebooks/NumberTheoreticFunctions/TotientFunction.nb.

For more information, see Eric's MathWorld entry http://mathworld.wolfram.com/TotientFunction.html.

©2008 Wolfram Research, Inc. except for portions noted otherwise

Plot

<<Utilities`Plot`

IntegerListPlot[EulerPhi[Range[100]],AxesLabel->TraditionalForm/@{n,EulerPhi[n]}]

Generating Functions

Generating Function

Sum[EulerPhi[n]x^n,{n,∞}]//FullSimplify

GeneratingFunction[EulerPhi[n],n,z]

ExponentialGeneratingFunction

Sum[EulerPhi[n]((x^n)/(n!)),{n,∞}]

DirichletGeneratingFunction

Sum[((EulerPhi[n])/(n^s)),{n,∞}]

Lambert Series

Sum[((EulerPhi[n](x^n))/(1-(x^n))),{n,∞}]

Special Cases

(EulerPhi[p])==p-1

FunctionExpand[EulerPhi[p],p∈Primes]

(EulerPhi[(p^a)])==(p-1) (p^(a-1))

FunctionExpand[EulerPhi[p^a],p∈Primes&&a∈Integers&&a>0]

Simplify[%]

(EulerPhi[(n^k)])==(EulerPhi[n]) (n^(k-1))

FunctionExpand[EulerPhi[n^k],(n|k)∈Integers&&n>0&&k>0]

Subtract@@@Flatten[Table[{EulerPhi[(n^k)],(n^(k-1))EulerPhi[n]},{k,5},{n,5}],1]//Union

Sums

DivisorProduct[n_, f_:Identity, cond___]:=Exp[DivisorSum[n,Function[x,Log[f[x]]],cond]]

(∑_n^∞)((EulerPhi[n])/(n^s))==((ζ(s-1))/(ζ(s)))

Sum[((EulerPhi[n])/(n^s)),{n,∞}]

n DivisorProduct(n,1-(1/(#1))&,PrimeQ[#1]&)==(EulerPhi[n])

n DivisorProduct[n,1-(1/(#))&,PrimeQ[#]&]

Table[(E^(DivisorSum[n,Log[(1-(1/(#1)))]&,PrimeQ[#1]&])) n,{n,10}]

n Exp[DivisorSum[n, Log[1 - 1/#1] &, PrimeQ]]

Table[n Exp[DivisorSum[n, Log[1 - 1/#1] &, PrimeQ]],{n,10}]

EulerPhi[Range[10]]

Subtract@@@Table[{EulerPhi[n],n DivisorProduct[n,1-(1/(#))&,PrimeQ[#]&]},{n,1000}]//Union

DivisorSum[n,(EulerPhi[#1])&]==n

DivisorSum[n,EulerPhi[#]&]

DivisorSum[n,EulerPhi]

DivisorSum[n,#1 (MoebiusMu[(n/(#1))])&]==(EulerPhi[n])

DivisorSum[n,# MoebiusMu[(n/(#))]&]

(∑_k^n)Boole[CoprimeQ[n,k]]==(EulerPhi[n])

Sum[Boole[CoprimeQ[n,k]],{k,n}]//InputForm

Subtract@@@Table[{Sum[Boole[CoprimeQ[n,k]],{k,n}],EulerPhi[n]},{n,1000}]//Union

(∑_k^n)Boole[gcd(n,k)==1]==(EulerPhi[n])

Sum[Boole[GCD[n,k]==1],{k,n}]//InputForm

Subtract@@@Table[{Sum[Boole[GCD[n,k]==1],{k,n}],EulerPhi[n]},{n,1000}]//Union

Subbarao

sub[n_]:=Mod[n DivisorSigma[1,n],EulerPhi[n]]

Table[sub[Prime[n]],{n,100}]

Select[Table[{n,sub[n]},{n,100000}],!PrimeQ[#[[1]]]&&(#[[2]]==2||(EulerPhi[#[[1]]]==2&&#[[2]]==0))&]

Subbarao states that solutions are 4, 6, 22.

Arithmetic Progressions Having the Same Value

t=EulerPhi[Range[10^7]];//Timing

Take[t,50]

s=Split[t];//Timing

Max[Length/@s]

Pairs

pairs=Position[Length/@Take[s,10^4],2,{1}]//Flatten

Transpose[{s[[#,1]],1+Plus@@(Length/@Take[s,#-1])}&/@pairs]

Triples

Position[Length/@s,3,{1}]//Flatten

Guy

EulerPhi/@{5186,5187,5188}

EulerPhi/@{25930,25935,25940,25942}

EulerPhi/@{404471,404473,404477}

McCrainie

EulerPhi/@Range[583200,583350,30]

Special Identities

Even Arguments

Table[EulerPhi[2n],{n,20}]

Odd Values

Position[Table[EulerPhi[n],{n,10^6}],_Integer?OddQ]//Flatten//Timing

Values of n s.t. ϕ((Subscript[σ, 1])(n))==n

Position[Table[EulerPhi[DivisorSigma[1,n]]-n,{n,10^5}],0,{1}]//Flatten//Timing

Trailing Zeros for p q

Do[
Print[{i,EulerPhi[Random[Integer,{1,10^30}]Random[Integer,{1,10^30}]]}//Timing],{i,10}]

Inequalities

Show[Graphics[{
{Blue,Line[{{0,#},{5000,#}}]&[Exp[-EulerGamma]]},
PointSize[.005],Red,Point/@Table[{n,((Log[Log[n]])/n)EulerPhi[n]},{n,2,5000}]}],Axes->True,
AxesLabel->TraditionalForm/@{n,Log[Log[n]]/n EulerPhi[n]}
]

1+Position[Table[EulerPhi[n]<(n/(Exp[EulerGamma]Log[Log[n]])),{n,2,2000}],True]//Flatten

Function[n,EulerPhi[n]<(n/(Exp[EulerGamma]Log[Log[n]]))]/@{1,2,3,4}

http://functions.wolfram.com/NumberTheoryFunctions/EulerPhi/29/0003/

1+Position[Table[EulerPhi[n]<(n/(Exp[EulerGamma]Log[Log[n]]+(2.50637/(Log[Log[n]])))),{n,2,10^5}],True]//Timing

1+Position[Table[EulerPhi[n]<(n/(Exp[EulerGamma]Log[Log[n]]+(2.50637/(Log[Log[n]])))),{n,2,10^6}],True]//Timing