Euler's totient product formula Created 2026-10-20 Updated 2026-11-05
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 .
Euler's totient function counts the integers in a complete complete residue system that are coprime to the modulus:
If the prime factorization is with distinct prime numbers , Euler's totient product formula is
In particular, . Adjoining the prime factor changes neither the odd factor nor its count of units, since . The product formula gives
This is a positive integer distinct from , as required.
Rosser–Schoenfeld totient bound Created 2026-10-07 Updated 2026-11-05
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.