Euler's totient function is the arithmetic function
It counts the congruence classes modulo represented by integers coprime to . In particular, , since . For , the coprime integers among are , so ; they form a reduced residue system. [ref]
Counting these congruence classes is useful because they are exactly the classes with modular multiplicative inverses. Their number supplies the exponent in Euler theorem. Möbius inversion gives the product formula
where runs over distinct prime factors of . Thus for prime powers with , and . The product for is an empty product, so it gives the same convention .
The prime-power formula and multiplicativity of Euler's totient function imply . For a prime with positive exponents in the inputs, both local products equal . If one exponent is zero, the equality is immediate from .
The totient divisor-sum identity and multiplication of absolutely convergent Dirichlet series give the quotient for . The bound proves convergence there. The simple pole of the Riemann zeta function at one makes the quotient unbounded as real . Since the coefficients are nonnegative, convergence at two would bound all these larger-real-part values, a contradiction. Thus the abscissa of absolute convergence of a Dirichlet series is two.
For a positive integer , Euler's totient product formula is
with the product over distinct prime divisors. Among the residues , a fraction is divisible by . Inclusion-exclusion over the prime divisors removes exactly those residues not coprime to .
For , the formula gives , corresponding to . It gives and shows that the Euler totient function is multiplicative on coprime integers. For , the empty product gives .
Given a positive integer , find all positive integers satisfying . For every prime divisor of a solution, divides , so the possible primes lie in the finite set . Search can then combine the prime powers whose totient contributions multiply to .
The summatory totient function is . It counts the coprime ordered pairs with . The identity yields for a positive integer .
A smoothed form of the summatory totient function satisfies
Use the Dirichlet series and the kernel to write the left side as a vertical contour integral. Move the line from real part greater than two to . The only crossed pole is at two, with residue ; the remaining vertical integral is by the standard zeta bounds in the half-strip. If and , positivity of the summands makes nondecreasing. The backward and forward difference quotients of bound . Insert , then let the relative difference-quotient step tend to zero, proving the displayed asymptotic. This monotone integral Tauberian lemma justifies the passage from a smoothed estimate to an unsmoothed one.
For an integer , the coresilience is
where is Euler's totient function.[ref] It is related to the resilience of a denominator , but is not its complement:
For a prime number , but , rather than zero. For the composite number fifteen, and .
As , the value is a unit fraction precisely when divides . A composite prime power with cannot qualify: its value is , already a reduced fraction with numerator greater than one. This excludes an entire family of composite numbers before a search.
For an integer , the resilience of a denominator is the fraction of its proper fractions already in lowest terms. The fraction is a reduced fraction exactly when and are coprime, so
where is Euler's totient function.
For , the allowed numerators are , giving . A prime denominator has resilience one. Conversely, a composite number has a proper prime divisor , and is among the listed fractions but is not reduced; thus its resilience is strictly less than one.
The prime factorization formula gives
The correction comes from sampling the positive proper numerators, rather than all residue classes. The related coresilience uses .
The sequence obtained by iterating Euler's totient function on a positive integer. Since for , the sequence reaches 1. Counting both endpoints gives the length recurrence relation and ; increasing order of therefore suffices for dynamic programming.
The divisor sum of Euler's totient function is the identity arithmetic function:
Equivalently, under Dirichlet convolution, with the constant-one arithmetic function. [ref]
To see why, group the integers by . Each is a positive integer divisor of . Within its group, with and , by the scaling identity for greatest common divisors. Dividing by gives a bijection with the integers counted by . The groups form a partition of a set, so
For , the groups with greatest common divisor are respectively . Their sizes are , totaling . Möbius inversion reverses this divisor sum to recover Euler's totient function from .
The map is a bijection of the integers between one and that are coprime to . If their sum is , this bijection gives , so . This works even at , where the single residue is fixed. The same identity follows from the weighted inclusion-exclusion principle by excluding multiples of the prime factors of .
If is odd, its Euler totient function is even and cannot divide . Otherwise write with odd primes and . Comparing powers of two in gives . Thus there is at most one odd prime , with . Since divides , it divides , and is coprime to ; with only the prime factors available it must be a power of two. Hence and . Conversely, for the prime-power totient formula verifies divisibility for , and is immediate.
Write and , with . The prime-power formula for the Euler totient function gives an integer contribution to from each prime: it is when , and when . Multiplying proves the divisibility assertion, including with .
For every integer , the Rosser–Schoenfeld totient bound states
where is Euler's totient function, is the Euler--Mascheroni constant and the logarithms are natural logarithms. The original theorem bounds above; its positive right side can be inverted to obtain this lower bound.[ref]
Thus the fraction of congruence classes modulo which are units is . It can be much larger: for a prime number it equals .
For a positive integer with , the Euler's totient product formula also gives : the product for omits some factors from the product for . A certified lower estimate for the ambient value therefore controls every divisor ratio, including , without evaluating at small values.
List the distinct prime divisors of in increasing order. The th is at least , and . The Euler totient function product formula gives . This elementary bound is sufficient to show inverse-polynomial success probability for coprime phase labels in quantum order finding.
For coprime positive integers , Euler's totient function satisfies
The Chinese remainder theorem gives a bijection from congruence classes modulo to pairs of congruence classes modulo and . A class is a unit modulo exactly when both component classes are units, because being coprime to is equivalent to being coprime to each factor. Counting these pairs proves the identity. The case where a factor is one follows from .
For example, . The coprimality assumption matters: whereas . Thus the Euler totient function is a multiplicative function, rather than a completely multiplicative function.
For each positive integer , only finitely many satisfy . Indeed, every prime has , and the exponent of in is bounded because .

Ancestors (4)

  1. Number theory
  2. Area of mathematics
  3. Mathematics
  4. Home

Synonyms (5)

Discussion (0) New discussion

There are no discussions about this article yet.

Articles by others on the same topic (0)

There are currently no matching articles.