BCH code Created 2026-09-24 Updated 2026-11-05
Let be a finite field, let be coprime to , and choose an element of multiplicative order in an field extension. A BCH code of length , starting exponent , and design distance is the cyclic code whose generator polynomial of a cyclic code iswhere is the algebraic minimal polynomial of over . Equivalently, is the least-degree monic polynomial over the base finite field vanishing at consecutive powers. This least-degree condition distinguishes the BCH code from its proper cyclic code subcodes with additional zeros. The BCH bound gives minimum Hamming distance at least .
For example, over the field with two elements, let and let be a polynomial root of . The roots and have the same algebraic minimal polynomial, so and give , a Hamming code of length seven.[ref]
Shift-Register Synthesis and BCH Decoding by James L. Massey. Sections IV–V: BCH codes and synthesis-based decoding
Candidate-denominator gcd post-processing Created 2026-10-06 Updated 2026-10-14
After continued-fraction recovery in quantum order finding, an even candidate denominator can be used to try the displayed greatest common divisors. Return only a divisor strictly between one and . If is the true even multiplicative order with a nontrivial halfway power, success follows from factor extraction from an even modular order. A candidate that is not a period can occasionally still yield a factor; testing before the gcds therefore changes single-run success probabilities. The output-factor check guarantees correctness in either convention.
Carmichael function Created 2026-09-24 Updated 2026-10-20
For an integer , the Carmichael function is the exponent of a finite group for the unit group : the least positive integer for whichHere the greatest common divisor condition selects the units. Euler's totient function counts them; the Carmichael function gives their least common return exponent.[ref]
Modulo eight, the units are , and their squares are all congruent to one. Their multiplicative orders are , so although . Modulo fifteen, the units have multiplicative orders . For example, the powers of two return through . Thus although ; the multiplicative order of four is only two.
The three quantities are related byA common return exponent must be a multiple of every multiplicative order, hence of their least common multiple. Conversely, that least common multiple makes every unit return to one. Lagrange's theorem makes each multiplicative order divide the group order , proving the final divisibility. The Carmichael function applies to all units at once, while the multiplicative order concerns a chosen unit.
For the prime factorization with distinct prime numbers and , the formulas areThese are least common multiples, rather than products: . The convention handles the trivial case separately.[ref]
The Chinese remainder theorem for unit groups explains the least common multiple: a power returns to one in every prime power component exactly when it is a multiple of each component's exponent of a finite group. For an odd prime power, the unit group is a cyclic group of group order . For , the unit group modulo is a direct product of groups , generated by the classes of and five, so its exponent of a finite group is .[ref]
A Computational Introduction to Number Theory and Algebra by Victor Shoup. Section 7.5, pp. 203–205, Theorem 7.28 and its proof
This gives a uniform reduction for modular exponentiation: for a unit and a nonnegative integer , reduce modulo . For example, because . The unit hypothesis matters: , but . Computing the formula assumes the prime factorization is available. The same common-exponent viewpoint explains Carmichael numbers: a composite number passes the Fermat primality test for every unit base exactly when . For example, .
Decimal period from multiplicative order 2026-10-14
For a reduced fraction with , , and coprime integers, its decimal representation repeats immediately after the decimal point. The shortest repeating block has lengthHere denotes multiplicative order, and denotes Euler's totient function. Changing the numerator preserves the decimal period as long as the fraction remains reduced.[ref]
For example, long division of gives the remainders , with emitted digits . ConsequentlyEach remainder determines both the next digit and the next remainder; returning to one restarts the same six steps.
Long-division remainders explain the six-digit repeat of one seventh and the two-digit prefix of one twenty-eighth
. Details. More generally, initialize long division with . At each step, division with remainder givesso . Since are coprime integers, the modular inverse of shows that exactly when . To see why the digit block cannot repeat sooner than the remainders, a purely repeating decimal with a block of digits represents for an integer . A reduced fraction with that value forces . Hence the shortest digit repeat and the multiplicative order coincide.
Knowing the decimal period predicts how many digits must be computed and stored: one block determines the whole repeating decimal. It also constructs the block directly. With , the integeris the block, padded on the left with zeros to digits. For , and , so the block is and . Reduction matters: has decimal period one, whereas .
If the reduced denominator contains prime factors two or five, ten has no multiplicative order modulo that whole denominator. WriteThe decimal preperiod has exactly digits. If , the remaining repeating decimal has decimal period . For instance, gives : two prefix digits, then six repeating digits. If , the decimal representation is a terminating decimal with exactly fractional places. We use the representation ending in zeros, rather than its alternative ending in nines; for example terminates after three places.
A short derivation explains both cases. After digits, multiplying the reduced fraction by and discarding its integer part leaves a reduced fraction whose denominator is . This denominator first becomes coprime to ten at . It then equals , giving an immediate repeat when , or an integer when . The same long division argument works for positional notation in any base : for a reduced denominator coprime to , the shortest repeating block has length .
Euler's theorem Created 2026-10-03 Updated 2026-11-05
For an integer modulus and an integer with greatest common divisor , Euler's theorem, also called the Fermat-Euler theorem, statesHere Euler's totient function counts the units in the unit group . These congruence classes have modular multiplicative inverses, equivalently their representatives are coprime to . The guaranteed return to one permits exponent reduction for units.[ref]
For a prime number , , recovering Fermat's little theorem in the form when . Multiplying by and separately handling gives for every integer . For a composite number used as the integer modulus, a nonzero congruence class can be a nonunit.
Modulo twelve, the units have representatives , so Euler's totient function gives . Multiplication by five producesThus this permutation has two permutation cycles, each of length two. In particular , and the guaranteed return follows. The number of units need not be the length of one permutation cycle. Modulo fifteen, multiplication by seven similarly gives the two permutation cycles and , covering all eight units. The powers of seven follow the permutation cycle containing one; the other permutation cycle shows that these powers do not visit every unit.
There is a stronger obstruction for a nonunit than just an occasional failed calculation. If a positive integer divides both and , then for every , so cannot be congruent to one modulo . For example, and , rather than one. Such a base has no multiplicative order modulo that integer modulus.[ref]
Orders of Units in Modular Arithmetic by Keith Conrad. p. 2, explanation following Example 1.8: a positive-exponent return to one forces coprimality
Exponent reduction for units 2026-10-14
For a unit modulo n and a nonnegative integer , division with remainder writes with . Euler's theorem then givesThis replaces a potentially enormous exponent by a small remainder. The exponent itself is reduced modulo Euler's totient function, while the powers are reduced modulo : these are different integer moduli.
For a worked modulo-fifteen calculation, seven is coprime to fifteen and . ThereforeUse exponentiation by squaring on the remaining exponent , reducing after each multiplication:Thus . Modular exponentiation supplies the computation; Euler's theorem supplies the optional shortening of its exponent. Exponentiation by squaring also works for nonunit bases, without using this shortening.
The guaranteed exponent is a common return exponent and an upper bound on the shortest period; it need not be that period. The multiplicative order is the least positive return exponent for the chosen unit. The Carmichael function is the least positive return exponent that works for every unit. Their precise relation isEither smaller return exponent can replace in exponent reduction for units. Modulo fifteen, , so gives immediately. For base four the multiplicative order is only two, smaller even than . A return at exponent eight alone does not prove that the multiplicative order is eight.[ref]
Actual power periods, Carmichael function exponents and Euler return exponents
. Each row lists powers from exponent zero through eight. Highlighted first returns identify multiplicative orders; the accompanying labels distinguish a chosen base's shortest period, the common exponent for all units, and Euler's totient function. Powers of the nonunit three modulo fifteen repeat after an initial term but never return to one at a positive exponent. The final calculation compares reduction of modulo eight and modulo four. Details. Fermat little theorem Created 2026-09-24 Updated 2026-10-14
For a prime number and an integer not divisible by , Fermat's little theorem states the modular congruenceEquivalently, for every integer , including and multiples of ,The first formulation follows from the second by multiplying by a modular multiplicative inverse of . Conversely, multiply the first by when ; when , both sides of the second are zero modulo . The divisibility condition in the first formulation is essential.[ref]
For , , so and . Also , while : a zero residue class cannot satisfy the first formulation. It does satisfy . A failure at a zero residue class therefore says nothing against a candidate's being a prime number.
The prime number is included. Its only nonzero residue class is one: every odd integer satisfies . Every integer also satisfies , because is even. Testing the first formulation with an even integer would violate its hypothesis.
The useful surprise is that every nonzero residue class returns to one at the same exponent , although its shortest return can be earlier. This gives exponent reduction for units: for a nonnegative integer , when . It also computes a modular multiplicative inverse as modulo , including . Repeated squaring makes these modular exponentiations practical.
In group theory, the nonzero residue classes form the multiplicative group of integers modulo n with , of group order . Lagrange's theorem says that the multiplicative order of divides , giving the guaranteed return. Euler's theorem extends this to a general integer modulus , using the units and Euler's totient function ; the Carmichael function gives the least common return exponent for all units. A nonzero residue class modulo a composite number need not be a unit.
Leonhard Euler's paper presented in 1732 and published in 1738 states a historical formulation: Theorem 1 says that powers with exponent leave zero or one upon division by a prime number . The preceding discussion states the difference-of-powers version and explicitly says that he does not have its proof.[ref]
Fermat number Created 2026-10-07 Updated 2026-10-13
A Fermat number is the positive integer , indexed by a nonnegative integer . The first five are , all prime numbers; the next is the composite number . This family offers a compact lesson in number theory: a very persuasive finite pattern can fail, while an exact divisibility relation settles a gigantic case with little computation.
Exact Fermat numbers: five initial primes, a composite sixth term, and rapidly increasing decimal lengths
. Details. Why does the exponent itself have the form ? Suppose is a positive integer with an odd integer factor . The polynomial factorization shows that is a proper divisor of . Consequently, if is a prime number, must be a power of two. That is a necessary condition, rather than a promise that the surviving candidates are prime.
The Fermat number product identity makes distinct Fermat numbers coprime integers. Thus every term has a prime factor absent from all earlier terms, whether or not that term is itself a prime number. This gives an explicit route to infinitely many different prime numbers, without establishing that infinitely many terms of this particular sequence are prime. Meanwhile the prime divisor of a Fermat number criterion filters possible factors through a small multiplicative order calculation.
The family also links arithmetic to Euclidean geometry: a constructible regular polygon can have a number of sides equal to a power of two times a product of distinct Fermat primes. The Gauss-Wantzel theorem gives the precise criterion. For instance, and qualify, but does not. The word "distinct" matters. Carl Pomerance describes this connection in Primality testing: then and now by Carl Pomerance (slide 18).
Historically, Leonhard Euler records Pierre de Fermat's proposed primality pattern, then refutes it by finding the factor of . His paper was presented in 1732 and published in 1738; those are different events, not competing dates for one publication.[ref]
Observations on a certain theorem of Fermat and on others concerning prime numbers by Leonhard Euler. pp. 1–2 and the publication note
A short modern check needs only two representations of :In modular arithmetic these give and . Substitution yields , so . This verifies the factor directly; it does not claim to reconstruct Euler's search process.
Fibonacci primitive root Created 2026-10-20 Updated 2026-11-05
A Fibonacci primitive root modulo an odd prime is a primitive root modulo n satisfying . Its powers obey , so the same multiplication that generates all nonzero residues also follows a Fibonacci recurrence.
For example, works modulo five: and its powers exhaust the nonzero residues. Solving the quadratic condition alone is insufficient; the multiplicative order must also equal . Away from , the quadratic has roots only when its discriminant five is a quadratic residue modulo .
Finite quotients of cyclic squaring presentations Created 2026-10-06 Updated 2026-10-14
A group presentation with a cyclic list of generators and relations has no nontrivial finite quotient of a group. In a finite image, all generator orders are odd. Choose the least prime dividing any nontrivial generator order and let be the predecessor of a generator whose order is divisible by . Conjugation by acts as squaring on , so the multiplicative order of modulo divides the order of . That multiplicative order is greater than one and divides , giving a prime divisor smaller than in the order of , a contradiction. This argument applies to any cycle length; it asserts absence of finite quotients, not infinitude of the presented group.
Lifting a primitive root to odd prime powers Created 2026-09-24 Updated 2026-11-05
Let be an odd prime and a primitive root modulo . Then is a primitive root modulo every prime power if and only if it is a primitive root modulo . In that caseThe condition at says with . The odd-prime case of the lifting-the-exponent lemma, obtained here by repeated use of the binomial theorem and then raising to an exponent not divisible by , givesHere is the prime valuation. To see the induction step, the first term in has prime valuation , while every later term has strictly greater prime valuation when is odd and .
Multiplicative order Created 2026-09-24 Updated 2026-10-13
For coprime integers with , the multiplicative order is the least positive integer such thatIt counts the distinct powers in the cyclic subgroup generated by the congruence class of . Thus it is an order of a group element in the unit group .[ref]
A Computational Introduction to Number Theory and Algebra by Victor Shoup. pp. 153 and 156–157, Theorem 6.29
For example, the modular exponentiation , starting at , produces . The first return to one takes three steps, so . Starting at the congruence class three and repeatedly multiplying by two instead gives : these are the other three units modulo seven, outside the cyclic subgroup generated by two.
Euler's theorem guarantees a return to one at exponent , where is Euler's totient function. Thus the multiplicative order exists for every unit.[ref]
Euler’s Theorem by Keith Conrad. p. 1, Theorem 1.2; pp. 2–3, permutation of the units and cancellation
In fact,By Lagrange's theorem, the size of the cyclic subgroup divides the size of the unit group, which is Euler's totient function. For two modulo seven, this is ; the multiplicative order need not equal Euler's totient function. If , its multiplicative order is one.The coprime integers hypothesis is necessary: if , any common divisor of and divides one. For instance, powers of two modulo eight give , with no positive-exponent return to one. This sequence eventually settles, but two has no multiplicative order modulo eight.
Nonzero residue permutation 2026-10-14
For a prime number and , multiplication by gives a permutation of the nonzero residue classes. For modulo seven, the representatives map to : the same collection in a different order. Repeating this permutation from one visits all six representatives before returning.
For modulo seven, the permutation cycles are instead and . The powers of two visit only the permutation cycle containing one, so their multiplicative order is three. Both permutation cycles return after three steps; applying the permutation six times still fixes every nonzero residue class. Fermat's little theorem guarantees a return at six, not that every base visits every nonzero residue class.
More generally, every permutation cycle of this map has length equal to the multiplicative order of : starting at a nonzero residue class , a return means , and its modular multiplicative inverse allows cancellation of . Thus the nonzero residue classes split into equal-length permutation cycles, which also explains the divisibility of the multiplicative order into .
The product argument gives a short proof outline. Since multiplication by is a permutation of the nonzero residue classes,Every factor is a unit, so their product has a modular multiplicative inverse and can be cancelled. This leaves . The whole argument works for , where the product is just one.[ref]
Order as the exact period of modular exponentiation Created 2026-09-24 Updated 2026-10-14
Let be coprime integers with , and let be their multiplicative order. For integers ,Negative exponents mean powers of the modular inverse of . Thus periodic modular exponentiation has smallest positive period , and are distinct congruence classes.[ref]
A Computational Introduction to Number Theory and Algebra by Victor Shoup. pp. 156–157, Theorem 6.29; multiplicative notation on p. 153
This lets a huge modular exponentiation reuse a short list: reduce its exponent modulo the multiplicative order, then look up the corresponding power. For example, gives , while gives . When the multiplicative order is unknown, Euler's theorem permits reduction modulo Euler's totient function, though that period may be longer. Repeated squaring remains useful when computing either the unreduced or the reduced power.
For a proof outline, multiply by the modular inverse of , leaving . Apply Euclidean division to write with . Then ; minimality of the multiplicative order forces . The reverse implication follows from . The coprime integers hypothesis enables cancellation: modulo eight, , but this repetition supplies no multiplicative order for two.
Order verification from divisors Created 2026-09-24 Updated 2026-11-05
Let be a unit modulo and let be a positive integer. To prove that is its multiplicative order, it is necessary and sufficient to checkThe first check makes the true order a divisor of . If , choose a prime divisor of ; then , contradicting the second check. Conversely, if , no smaller positive exponent can return to one.
For example, alone does not prove order six: the divisor gives and rejects it. The candidate three passes, since but . Once the prime factorization of is supplied, this certificate needs one modular exponentiation per distinct prime factor, plus the return check. The factorization itself is separate work. The candidate has no prime divisors and is accepted exactly when .
The fact that a nontrivial factor usually appears before a full return does not say that either event appears soon. Each iteration of the RSA cycling attack is inexpensive, but the number of iterations can be enormous. The multiplicative orders governing returns modulo and need not be small, and writing down a large return exponent does not provide a fast way to search the preceding iterations.
If this procedure factored arbitrary well-generated RSA cryptosystem moduli in feasible time with substantial success, it would solve the associated integer factorization problem efficiently. If it instead rapidly returned the predecessor of a ciphertext without factoring, it would solve the RSA inversion problem. Both are intended to be infeasible for appropriate parameters. Efficient integer factorization certainly breaks RSA cryptosystem security; the reverse implication for general RSA inversion problem algorithms is not known.
Thus the stated observation alone provides no serious general attack on well-generated parameters. It also does not prove a lower bound: special moduli or messages with short cycles can be weak, and the hardness claims are computational assumptions.
Past exam of the mathematics course of the University of Cambridge 2001 ia Paper 4 7E b Solution Created 2026-09-24 Updated 2026-10-14
Let be the multiplicative order of modulo . Use Euclidean division to write , . Since ,If , minimality of forces , so divides . Conversely, immediately gives . For negative integers , powers are interpreted using the multiplicative inverse and the same argument applies.
Past exam of the mathematics course of the University of Cambridge 2001 ia Paper 4 7E c Solution Created 2026-09-24 Updated 2026-10-14
If with an odd prime, then but . The multiplicative order consequently divides four and is neither one nor two, so it is four. The preceding divisibility result makes necessary.
For sufficiency, suppose and put , an even integer. Pair opposite factors in the factorial:Wilson's theorem gives , explicitly producing a square root of minus one modulo a prime. Thus
Past exam of the mathematics course of the University of Cambridge 2002 ia Paper 4 8B Solution Created 2026-09-24 Updated 2026-10-14
For , Euler's theorem allows , since are coprime integers. At every congruence holds and one may take . Let be the multiplicative order of modulo . Write a nonnegative exponent with using the Euclidean division. Then , so implies by minimality of . Thus . Negative exponents, if included, give the same conclusion using the inverse residue of .
A prime divisor of a Fermat number is odd, and satisfies . Therefore , so its multiplicative order divides . It does not divide , since modulo the odd prime. Every divisor of is a power of two, henceBy Fermat's little theorem and the divisibility just proved, , giving .
Past exam of the mathematics course of the University of Cambridge 2002 iii Paper 33 5 Solution Created 2026-10-03 Updated 2026-10-14
Let be a unitary operator and suppose initially that the target is an eigenstate with , . Use control qubits, so . Hadamard gates prepare the uniform superposition . For each binary control position , apply the controlled unitary gate . The resulting state isApply the inverse quantum Fourier transform, with convention , and measure the control. The exact amplitude and probability areFor an exactly representable phase , orthogonality of roots of unity makes the outcome certain. Otherwise the finite geometric series givesThe estimate is , with phases interpreted modulo one.
To prove an error bound, choose a nearest label to on the circular grid and put in the interval . For , concavity of sine on gives , while . Therefore the nearest-integer success bound for quantum phase estimation isHere . At an exact grid point the probability is one. If two nearest labels tie, either one separately has the displayed lower bound.
For high confidence one can prove a stronger quantum phase estimation tail bound. Let be the centered distance between and , chosen with . The denominator estimate implies away from the exact-phase case. A label at circular integer distance from has , and there are at most two labels at each such distance. For , summing the tails givesOn the complementary event the circular phase error is at most . Thus, for desired bits of accuracy, take with and to obtainTaking makes the right side at most . This adds only control qubits. Efficient QFT is not by itself a guarantee of efficient controlled powers of an arbitrary : implementing them by repeated oracle calls uses calls. The modular-arithmetic application has efficient powers, as follows.
Assume and , and let be the multiplicative order of modulo . Define the unitary operator on , and extend it as the identity on unused computational-basis labels of the binary register. Coprimality makes multiplication a permutation, so this extension really is unitary. The orbit of consists of the distinct states . Its modular multiplication eigenstates areThe last relation follows by shifting the index cyclically; orthogonality follows from the finite Fourier sum. We do not need to know to prepare one of these eigenstates: the readily prepared target obeysRunning quantum phase estimation on this state produces the mixture of the eigenphase distributions, each with weight , because the target eigenstates are orthogonal. Thus it samples a uniformly random phase label and estimates with the bounds just proved. Equivalently the state before the inverse QFT is , which is obtained by quantum modular exponentiation directly.
The controlled power multiplies by , whose constant is computed by repeated squaring. Under the assumed efficient modular exponentiation, these controlled multiplications and the QFT use a number of gates polynomial in the register lengths. Taking requires only phase qubits. The nearest-label event has probability at least and yields an estimate within of . Since , continued-fraction recovery in quantum order finding then identifies the reduced fraction . The denominator is , not necessarily : when and are coprime it is the desired order, and when they are not it is only a divisor. One may test candidate denominators using modular exponentiation and repeat with fresh samples; denominators from successful samples can also be combined by a least common multiple. The probability of a nearest-label sample with coprime to is at least . These qualifications explain exactly what the phase estimate yields without falsely assuming that the unknown order or an eigenstate was available at the start.







