EulerPhi

Notations

Traditional name

Traditional notation

Mathematica StandardForm notation

Primary definition

Specific values

Specialized values

Values at fixed points

General characteristics

Domain and analyticity

ϕ(n) is a nonanalytical function which is defined only for integer n.

Symmetries and periodicities

Parity

ϕ(n) is an even function.

Symmetry

No symmetry

Periodicity

No periodicity

Series representations

Other series representations

Product representations

Identities

Functional identities

Summation

Finite summation

Infinite summation

Asymptotic finite summation

Asymptotic infinite summation

Operations

Limit operation

Representations through equivalent functions

With related functions

Inequalities

Zeros

Other identities

Congruence properties

Theorems

Fermat-Euler theorem

(a^(ϕ(m)))≡1(mod m)/;    gcd(a,m)==1

Generalized Fermat-Euler theorem

(a^(k+ϕ(b))) mod b==(a^k) mod b/;gcd((a^k),b)==1∧gcd((a^(k+1)),b)==1∧k∈(SuperPlus[ℕ]).

The solution of a linear congruence

The solution of (a x-b) mod m==0 is given by x==(b/d)((((a/d)))^(ϕ((m/d))-1))mod (m/d)/;d=gcd(a,m)∧(b/d)∈ℕ.

Number of different values of ϕ(k) for k≤n

The number V(x) of different values occurring in the list  {ϕ(1),ϕ(2),…,ϕ(x)} behaves asymptotically as

where

Farey fractions

The number of irreducible fractions between 0 and 1 with denominator n is ϕ(n).

Generators of cyclic groups

ϕ(n) is the number of generators of a cyclic group of order n.

Carmichael conjecture

For every n it is possible to find an m (n≠m), such that ϕ(n)==ϕ(m).

Number of necklaces

The number n of unique fixed necklaces of length l which can be made out of b different beads is n==(1/l)(∑_(d|l))ϕ(d) (b^(l/d)).

Probability that two randomly choosen positive integers are relatively prime

The probability (Subscript[p, 2 ]) that two randomly choosen positive integers (Subscript[n, 1])and (Subscript[n, 2]) ((Subscript[n, 1]), (Subscript[n, 2])<x) are relatively prime (gcd((Subscript[n, 1]),(Subscript[n, 2]))==1) is given by

(Subscript[p, 2])=(1/(x^2))(-1+2(∑_(k=1)^(⌊x⌋))ϕ(k))(Underscript[≈, x->∞])(1/(ζ(2)))==(6/(π^2)).

Prime roots

All integers n of the form 1, 2, 4, (p^k), 2(p^k) where 2p+1∈ℙ, k∈ℕ, have ϕ(ϕ(n)) different primitive roots.

History

– L. Euler (1760, 1763)
– C. F. Gauss (1801) introduced the symbol ϕ
– J. J. Sylvester (1879) introduced the name "totient function"
– E. Cesaro (1888) evaluated asymptotics for cumulative sums
– E. Landau (1900)

Copyright