For every there is such that, for ,
Here is the Chebyshev function in an arithmetic progression and is the Euler totient function. Partial summation gives the corresponding result for the prime-counting function and the offset logarithmic integral function. The theorem controls the total error over many moduli; it need not give the same bound for each individual modulus.
Brun–Titchmarsh theorem 2026-10-06
For and , the prime-counting function in an arithmetic progression satisfies
The denominator involves the Euler totient function and the length-to-modulus ratio. In particular, for with fixed , this is .
Counting cyclic subgroups by their generators Created 2026-10-06 Updated 2026-11-05
In a finite group, a cyclic subgroup of order has exactly generators, where is the Euler totient function. Each element generates exactly one cyclic subgroup, so dividing the number of elements of order by counts these subgroups. Include the identity subgroup using and . In a symmetric group, element counts come from cycle type and order of a group element is the least common multiple of cycle lengths.
Elementary totient-ratio lower bound Created 2026-10-06 Updated 2026-10-07
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.
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 .
An element of the additive finite cyclic group is a generator of a group precisely when . The order of an element of a finite cyclic group proves this immediately: its cyclic subgroup has size , and this equals exactly when the greatest common divisor is one. There are therefore choices, where is the Euler totient function.
For , the two choices are and , so . For , they are . Starting from zero and repeatedly adding modulo eight gives , visiting every element once before returning. By contrast, adding gives and misses the odd integers represented in the other coset.
If the cyclic group is written multiplicatively as with of order , the same statement says that is a generator of a group exactly when and are coprime. This changes notation without changing the calculation.
Integers whose totient divides them Created 2026-10-14 Updated 2026-11-05
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.
Min_25 sieve Created 2026-10-20 Updated 2026-11-05
The Min_25 sieve computes summatory multiplicative functions by isolating weighted prime sums and then restoring composite contributions. A useful basic form applies when for primes , the degree is small, and values on prime powers can be computed efficiently. The formulas below explain the two stages; optimized implementations differ in scheduling and cost.[ref]
Use quotient arguments . There are distinct values: indices at most contribute that many, and larger indices yield values below . The floor function identity keeps later quotients in this table.
For each exponent , initialize . Process primes in increasing order, and eligible in decreasing order, applying
This removes composites whose smallest prime factor is . The subtraction inside parentheses excludes earlier primes from the possible cofactors. Decreasing ensures each smaller argument still has its pre- value. After sieving, is the desired sum of over primes up to .
To restore composites, let be the th prime and let sum over with every prime factor greater than . Set for . Otherwise its prime contribution is , and add
Unique decomposition by smallest prime factor and its full exponent proves this recurrence: mixed numbers use the first term, pure powers use the second. With , and , the answer is . No complete-multiplicativity assumption is needed.
For the Euler totient function up to six, the prime contribution is . The composites add , and gives total twelve. This independently chosen small example checks that prime powers and mixed products are both counted once.
Multiplicativity of the Euler totient function Created 2026-09-24 Updated 2026-11-05
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 distinct prime numbers , compute the Euler totient function
The RSA cryptosystem private exponent is a modular multiplicative inverse of the public exponent:
Use the extended Euclidean algorithm on and . It produces integers with , and reducing modulo gives a suitable positive . Searching through possible exponents is unnecessary.
To see correctness even for a plaintext sharing a factor with , write . Modulo , either or Fermat's little theorem gives ; the same holds modulo . The Chinese remainder theorem then gives . One may alternatively invert modulo , but inversion modulo is sufficient for this paper.
The Selberg upper-bound sieve replaces an exact but long inclusion-exclusion expansion by a short nonnegative square, and then minimizes its main term. For an interval , the count of multiples of every integer is
Crucially the remainder bound is independent of .
Let and take real weights , supported on squarefree , with . If , the sum of these weights over divisors of is just one; for all other its square is nonnegative. Thus
Expanding and counting common multiples gives
This separates the local density from a uniform interval error. The weights will be chosen to minimize .
The Euler totient function identity yields the Selberg sieve diagonalization
Only squarefree occur. Inverting this finite triangular sum by Möbius inversion gives
Write . The Cauchy-Schwarz inequality gives , with equality at . The inverse formula then produces the optimal Selberg sieve weights
The constraints are satisfied, since the diagonal transformation is invertible and .
We need the leading constant, not just . Here is an elementary proof of the Selberg sieve denominator asymptotic. For define the multiplicative arithmetic function by
Checking the prime-local factors shows . Also : the local factors for absolute values differ from one by , and their logarithmic first moments sum . The signed local sums are all one, so absolute convergence gives . Using the harmonic number estimate,
For the last equality, is bounded and is bounded too.
The optimal Selberg weights have modulus at most one. To prove this here, for squarefree use . The product is the sum of over , , , with squarefree. All are distinct squarefree integers at most , and so these are a subset of the terms of . The displayed weight formula now gives . Consequently
Every prime in the interval exceeding survives the sieve; at most smaller primes must be restored. Choose . Then
and the uniform interval bound from optimal Selberg weights follows:
All constants are independent of . Given , make the absolute error in the coefficient smaller than by choosing large enough. Uniformly for every and ,
A root of unity over a finite field is an element satisfying , with ; the algebraic closure is essential because all roots need not lie in the base field. Write and , where . In characteristic ,
The latter polynomial has distinct roots, since the derivative is nonzero at every root. Those roots are closed under multiplication and inversion and contain , so is a finite multiplicative subgroup of a field. The proof in the preceding solution makes it a cyclic group. In particular
This also explains why the coprimality qualification is needed.
The multiplicative group of a finite field is cyclic of order . It contains the entire group of th roots precisely when . For necessity, a generator of has order and Lagrange's theorem applies. For sufficiency, a cyclic group whose order is divisible by contains roots of ; since there are exactly roots in the algebraic closure, these are all of them. Hence the least positive extension degree is
Here is the multiplicative order of the residue class of modulo . If is coprime to , replace by . Existence of this order follows because is a unit modulo .
A primitive th root of unity over a finite field has multiplicative order exactly . If , no such element exists, since all roots have order dividing . If , choose a generator of . The element has order , so it is primitive precisely when . Therefore there are primitive roots, with the Euler totient function.
If is primitive of order , then exactly when , equivalently . The implication from that equality to membership follows because the roots of form , as proved in the preceding solution. Consequently
for , and the degree is one for . This is also the length of the finite-field Frobenius automorphism orbit of .
Using the same basis of as before, the fourth roots of unity are
There are four, they are already in , and the primitive fourth roots are the two vectors and .
For each , the product is precisely outside every , and is otherwise. It is therefore the indicator function of . Expanding the finite product gives
Multiply by and sum over the finite set . The product of indicator functions is the indicator function of the corresponding intersection, so
Here the empty intersection is , and the empty product is . Grouping the subsets by their cardinality gives the requested weighted inclusion-exclusion principle, with no contribution for .
Let be the finite set of distinct prime factors of , and work in . For put , including . Then , and an integer belongs to every for exactly when it is a multiple of . Thus the intersection has size . The complement consists precisely of the residues coprime to . Using weight gives
This proves the product formula for the Euler totient function without requiring to be squarefree.
For the weight , the sum over the multiples of any divisor in this interval is
The weighted inclusion-exclusion principle therefore gives
Since , is nonempty and the last sum is . The first factors as before, giving
This sum of reduced residues also follows by pairing the bijection ; at its sole fixed residue causes no problem because the sum of both copies still equals .
An equivalence relation is reflexive, symmetric and transitive: for all , one has ; implies ; and , imply . Define the equivalence class . Reflexivity puts in its class, so these classes cover and are nonempty. If and share , symmetry and transitivity give ; the same properties show that every element of either class is in the other. Thus two classes are equal or disjoint. The distinct equivalence classes form a partition of the set.
For the relation defined by a subgroup , proves reflexivity. If , its inverse belongs to , proving symmetry. If also , their product is , proving transitivity. Finally,
These are exactly the left cosets. The map , , is a bijection, with inverse . If is finite and has such cosets, their disjoint union gives . This proves the Lagrange theorem:
For , finitely many possible powers imply for some , so a positive power is the identity element. If its least positive exponent is , the powers are distinct: equality of two would produce a smaller positive exponent. They are closed under products and inverses by reducing exponents modulo , hence form the cyclic subgroup of cardinality . The Lagrange theorem gives , and consequently
Now take a positive modulus . On residue classes modulo , consider the classes with representatives coprime to . The following integer facts are used: multiplication is associative; reducing representatives respects products; a prime dividing a product divides a factor; and the Bezout identity gives when . If are coprime to , no prime divisor of divides , so their product class is again in the set. The class of is its identity element. The Bézout equation gives , and is also coprime to because any common divisor of would divide . Thus every class has an inverse, and these classes form the group of units modulo an integer.
Representing classes in gives precisely the group in the question; for this is the one-element group. Its cardinality is the Euler totient function . Applying the finite-group exponent result yields the Fermat-Euler theorem:
For the congruence is automatic.
The Fermat-Euler theorem states that, for a positive integer and an integer coprime to , , where the Euler totient function counts residue classes coprime to . The case is trivial. For , let be a reduced residue system. Multiplication by permutes it: equality of two resulting residues can be cancelled using the modular inverse of , and the products remain coprime to . Multiplying the residues before and after the permutation gives
Every factor on the right is a unit, so its product can be cancelled. This proves
The integer is prime: none of the primes up to divides it. Therefore . Apply the theorem to and use the supplied congruence:
To connect this to individual digits rather than merely assert periodicity, use long-division remainders and
Induction gives . Since is coprime to , no remainder is zero. The congruence above therefore implies for every , using the unique representative in . In particular
Hence
This is the mechanism of decimal period from multiplicative order: the period divides .
For a positive integer , a Dirichlet character modulo is a group homomorphism , extended periodically to the integers and set equal to zero on integers not coprime to . Its nonzero values are roots of unity. For , its Dirichlet L-function is the absolutely convergent Dirichlet series
Complete multiplicativity of proves the Euler product by expanding each factor as a geometric series and applying unique integer factorization; absolute convergence justifies these rearrangements.
Suppose is a nonprincipal Dirichlet character. Choose a unit with . Multiplication by permutes a complete residue system, so , and the sum is zero. Consequently is bounded: complete periods contribute zero and the remaining incomplete period has at most terms. The Abel summation formula gives, initially for ,
For the integral converges, locally uniformly together with its derivatives in , because on a compact set with the differentiated integrands are bounded by constants times . Thus holomorphy of a Dirichlet series from bounded partial sums proves
For a nonreal , the character is also nonprincipal. The supplied logarithmic Euler product yields, for real ,
At a prime dividing the numerator is . At every other prime put ; then the numerator is . This Euler product positivity for L-function nonvanishing proves that the product inside the logarithm is at least one. If , its holomorphy would give . Meanwhile is bounded near one and the Riemann zeta function has a simple pole there. The product would therefore be and tend to zero, a contradiction.
For a real nonprincipal , suppose instead that . The product would then be holomorphic on the whole half-plane , because the zero cancels the only zeta pole there. In it has coefficients
These are nonnegative zeta-times-real-L coefficients. They are multiplicative, and their prime-power values are if , one or zero according as is even or odd if , and one if . In particular and for every .
The Taylor series of the assumed holomorphic about converges in the disk . Termwise differentiation of its absolutely convergent Dirichlet series at gives . Evaluate the Taylor series at and apply the Tonelli theorem to the resulting nonnegative terms:
This contradicts holomorphy at . The argument is the positive-coefficient mechanism of the Landau theorem for a Dirichlet series with nonnegative coefficients, with the needed step proved explicitly. Combining the real and nonreal cases gives the nonvanishing of a nonprincipal Dirichlet L-function at one:
Now let be coprime to . The Dirichlet theorem on primes in arithmetic progressions asserts that infinitely many prime numbers satisfy . To prove it, separate the first-power terms in the given logarithmic Euler product:
For , the remainder is bounded uniformly by
For a nonprincipal character, holomorphy and nonvanishing near one give a local holomorphic logarithm. Along a short real interval to the right of one, this logarithm and the supplied continuous logarithm differ by a fixed integer multiple of . Hence the prime-character sum near one is bounded:
For the principal Dirichlet character ,
The latter follows from the simple zeta pole and the bounded remainder. Finally Orthogonality of Dirichlet characters gives
Here is the Euler totient function. The right-hand side tends to infinity as , whereas a finite set of primes would give a bounded left-hand side. Therefore
The cyclotomic Galois group theorem states
for coprime to , with , where is the Euler totient function.
Cyclic periodicity on implies that the least positive period divides : the shifts preserving the function form a subgroup of the cyclic group. Injectivity within one period says that distinct residue classes modulo have distinct function values. Write .
Prepare the uniform superposition state by applying the quantum Fourier transform to , and evaluate reversibly into a second quantum register. This is efficient because the given classical Boolean circuit can be converted into a reversible circuit, with its workspace cleaned by uncomputation. The resulting quantum state is
Measuring the function quantum register leaves a uniform coset state for some . The amplitude at after a quantum Fourier transform is
The finite geometric series is zero unless is a multiple of , and then equals . Thus a computational-basis measurement produces a uniform Fourier sample
The exact period recovery from a Fourier sample computes
A greatest common divisor is computable in time polynomial in . The candidate is always a divisor of the true period, and equals it precisely when is coprime to .
For the success flag, compute and compare with . If , injectivity within the first period makes these unequal. If , periodicity makes them equal, including . Hence accept and output exactly when this comparison succeeds; otherwise report failure. This is heralded exact quantum period finding when the period divides the register size, with no false acceptance. The case succeeds even on the sample .
The exact success probability is
where is the Euler totient function. For , the prime-product formula gives . A Rosser–Schoenfeld totient bound supplies the needed lower bound for large . Every single attempt, including verification, has the assumed polynomial-in- gate cost. Repeating times gives constant success probability with a certified result whenever one is found.
The printed in the totient hint should be a lower-bound statement, . Literally, is false: at primes , . Likewise the exact single-sample success probability need not be ; for prime period it tends to one. The useful intended guarantee is the displayed inverse-log-log lower bound, not a universal upper bound. If an algorithm satisfying the literal success upper bound is desired, one can additionally accept an otherwise certified run only when independent fair bits are all zero. This retains a detectable failure flag and polynomial runtime, and has success at most , but deliberately weakens the useful guarantee. The standard unsuppressed algorithm above gives the stronger intended performance. Small can be handled directly. Primary evidence for the totient lower bound is Theorem 15, equations (3.41)–(3.42), in denisevellachemla.eu/Rosser-Schoenfeld-1962.pdf .
The Fermat-Euler theorem states that, for an integer and any integer coprime to ,
where the Euler totient function counts the residue classes coprime to .
Let be representatives of these residue classes. Multiplication by gives a permutation of them: each remains coprime to , and implies by cancellation using the modular inverse of . Multiplying all the resulting modular congruences yields
The product is itself coprime to , so it has a modular inverse and can be canceled. This proves the Fermat-Euler theorem. For , the congruence is trivial; no separate argument is needed.
Use the positive-sign quantum Fourier transform
Orthogonality of the finite-group characters makes a unitary operator. Here is the least positive period. The injectivity within one period implies : write , . Periodicity gives , and injectivity forces . Put .
Start with two available computational basis states . Apply to the first register and query the modular-addition quantum oracle:
Measure the second register. For some , the first register becomes the normalized coset state
The quantum Fourier transform of a periodic coset state is
Indeed, the inner geometric sum vanishes unless the Fourier label is a multiple of . Measuring that label gives for a uniformly random . Compute, by the Euclidean algorithm,
Thus exact period recovery from a Fourier sample succeeds whenever is coprime to , and
Here is the Euler totient function. The classical number-theory input is the totient lower bound from the Mertens product: for sufficiently large , for an absolute , with the finitely many small cases handled separately. For recovery is certain; for its probability is . The useful asymptotic probability statement is a lower bound, hence notation; it can be much larger for particular periods, for example a prime period.
There is one oracle query, two Fourier transforms and two measurements. The final greatest common divisor and division use polynomial time in . This meets the specified primitive-operation model without assuming that an arbitrary- Fourier gate is free in another gate model. If a constant success probability is wanted, repeat independently times and return the least common multiple of the candidates: each candidate divides , and one successful sample makes that least common multiple exactly .