Motivation
A modular calculation may be easier in several small moduli than in one large modulus. Reconstruction is useful only if the local answers determine exactly one global residue. The Chinese remainder theorem supplies that guarantee and turns Bézout coefficients into an algorithm for combining partial information.
Primality testing asks a different question: does a modulus have the field properties that many modular proofs require? A failed modular identity can certify compositeness. A passed identity may merely say that this particular base did not expose a problem. We will prove precisely what two tests establish, rather than reverse a necessary condition into an unsupported primality certificate.
The preceding arithmetic chapter supplies Euclid, modular inverses and repeated squaring.
Definitions
Definition 9.1.1
(Congruence data and compositeness witnesses)
For an integer , means . A residue reconstruction problem specifies several such conditions on one unknown integer. A prime is an integer with exactly two positive divisors. A compositeness witness is data whose verified property, under a stated theorem, proves that an integer greater than one is not prime. A test passing for one base means only that no witness of that specified form was obtained.
Definition 9.1.2
(Strong probable-prime condition)
For odd , write uniquely , where is odd and . For a chosen integer base , a nontrivial gcd with immediately gives a factor. Otherwise set
Repeated squaring computes this chain. The strong probable-prime condition for this base is that or some for . Equality here uses standard representatives from zero through ; represents minus one. Passing is deliberately not called a primality proof.
Theorem/Proposition
Theorem 9.1.3
(Constructive Chinese remainder theorem)
Let be pairwise coprime, and let be integer residues. There is exactly one solution class modulo . Starting from , merge each new condition by computing
and replacing simultaneously by . The state always satisfies and represents exactly all solutions of the processed conditions.
Theorem 9.1.4
(Trial division is a deterministic primality test)
An integer is composite if and only if it has a prime divisor at most . Therefore testing integer divisors while gives a correct deterministic test. If all integers are tested rather than just primes, at most trial divisions are needed.
Theorem 9.1.5
(Failure of the strong condition proves compositeness)
Every odd prime satisfies the strong probable-prime condition for every permitted base. Hence, if a base has gcd one with and fails that condition, is composite. If an intermediate value satisfies , then is a proper nontrivial factor.
Proof sketch or proof idea
Proof
(Merging one condition)
For a CRT merge, the current conditions give exactly for integer . The new condition becomes . Coprimality makes invertible modulo , so there is one class . Consequently the merged solution class is modulo . The bounds on give . This proves initialization, preservation and uniqueness together. Pairwise coprimality ensures every later product remains coprime to the next modulus.
Proof X-ray
Where the merge uses coprimality
The proof reduces a system to one congruence by parametrizing: the processed conditions describe exactly , so the new condition becomes the linear congruence . Coprimality is used once, to make invertible modulo , which gives exactly one class . Since is a product of earlier moduli, pairwise coprimality gives . The range bounds close the argument: . Without coprimality the congruence for could have no solution or several classes.
Proof
(A smallest factor at most the square root)
For trial division, if is composite, write with . Then . A prime factor of is also a divisor of and is no larger than . Conversely a prime divisor no larger than is proper, proving compositeness. The integer comparison avoids relying on a floating-point approximation to the square root.
Proof
(A square-root chain ending at one)
For the strong condition, first recall Fermat's identity for a prime modulus. Multiplication by a nonzero residue permutes the nonzero classes, so multiplying that complete set and canceling its invertible product gives . Thus . If , let be the first index with . Its predecessor squares to one and is not one. In a prime field, forces or , so that predecessor must be minus one. Its index is smaller than , establishing the strong condition.
Proof
(Extracting a factor from a nontrivial square root)
For the factor claim, the congruence says . If , Bézout cancellation would force , contradicting . If that gcd were , we would have , also excluded. Therefore the gcd lies strictly between one and . This argument needs no assumption that the composite modulus is squarefree.
Proof X-ray
A necessary condition has a useful contrapositive
Prime moduli satisfy the strong condition because their only square roots of one are plus and minus one. A failed condition therefore proves the modulus is composite. The converse does not follow: a composite modulus may imitate the required chain for a particular base. The proof explains rejection, not automatic certification after acceptance.
Worked examples
Worked example 9.1.6
(A merge retains all solutions, not just one guess)
Solve and . After the first merge the state is . Since , the next correction is . The new state is . Checks give and . All solutions are with , not merely the displayed representative.
Worked example 9.1.7
(Compute locally and reconstruct a power)
Find . Modulo seven, six is minus one, giving residue six. Modulo eleven, Fermat reduces the exponent to three, giving . Starting with , solve , so and . Therefore . This exponent reduction is valid in the prime coordinates because six is coprime to both; reconstruction itself preserves the exact residue and introduces no numerical approximation.
Worked example 9.1.8
(A Fermat pass that the stronger chain rejects)
The composite satisfies , so . A base-two Fermat pass therefore does not prove primality. For the stronger test, , and , while . Neither tested chain entry is , and the initial entry is not one, so the strong condition fails. The nontrivial square root also yields , an explicit factor.
The reconstruction invariant is an exact specification
At every merge, the product describes the full period of all conditions already processed. The representative is kept in the standard range to bound its size and simplify later computations. It is not necessary to search all integers below the final product or to enumerate all combinations of local residues. Euclid supplies the one inverse needed at each step.
The initialization with product one is an internal state for an empty list of conditions. Every integer satisfies the empty list of conditions, so its solution class is all integers. The first actual modulus is still at least two, and the inverse of one modulo it is immediate. Separating that initialization from the public modulus definition avoids an unnecessary exceptional failure at the first merge.
The method can be checked independently by substituting the final representative into every input congruence. That verifies the construction, while the product-modulus uniqueness argument establishes completeness. Substitution alone would not prove that all solutions have been described. A program can expose both its representative and product so that these two parts of the mathematical specification remain visible.
Coprimality and representation costs
If two moduli share a factor, they impose overlapping information and may disagree. The product is then generally the wrong uniqueness modulus. A broader merge can use the linear-congruence solvability theorem and a least common multiple, but that is a different contract. The algorithm proved above must check its coprimality hypothesis rather than attempting to invert a nonunit.
The product's binary length is bounded by the sum of the binary lengths of the input moduli. This does not make arithmetic on that product constant-cost. Later inverses, products and reductions act on growing integers. The reconstruction makes a linear number of merges, but a bit-complexity statement must additionally account for the arithmetic routines. Keeping residues bounded after each merge controls storage without removing those arithmetic costs.
A fully specified strong test
Handle integers below two as nonprime, handle two and three as prime, and reject larger even integers with factor two. For a remaining odd integer, decompose one less than it into an odd factor times a power of two. Choose a permitted base and compute its gcd with the modulus. A proper nontrivial gcd is already a certificate; otherwise use repeated squaring to form the odd-power value and the subsequent square chain.
If the initial value is one, or any tested chain entry before the final exponent is minus one, report that the base passes. If neither occurs, report composite. One may stop early when a nontrivial square root of one appears and extract a factor as above. These exits have different meanings: one certifies compositeness, while the other records only a passed condition. An implementation should return different statuses rather than label both outcomes as answers to the same yes-or-no theorem.
The initial modular power and at most logarithmically many squarings require modular multiplications, using the previously proved repeated-squaring algorithm. Modular multiplication and gcd calculations still have their own bit costs. No probabilistic error bound is claimed here. Such a bound requires a separate theorem about how many bases can pass for a composite modulus, not merely repeated execution of the necessary-condition proof.
Why trial division remains worth understanding
Trial division has a simple complete correctness argument and produces a divisor when it rejects. Its limitation is its dependence on the numerical square root rather than the input's binary length. A prime input makes the loop test every candidate up to that threshold, which can be enormous relative to the number of digits. The method is nevertheless useful for small inputs and for removing small factors before applying other methods.
A faster rejection test and a complete deterministic primality proof are different goals. The strong condition gives efficient, rigorously justified rejection on many inputs, but one passed base does not settle every input. Trial division eventually settles every integer under exact arithmetic, but may take far more work. The student should identify what an algorithm certifies before comparing its speed.
Concept lensAlgorithmic
Certificates, tests and reconstruction answer different questions
CRT certifies that local values describe one global residue. A nontrivial gcd certifies a factor. A failed strong chain certifies that a prime-field implication has broken. A passed chain is a weaker outcome that needs additional mathematics before it becomes a primality guarantee. Keeping these outputs distinct prevents a useful algorithm from being credited with a theorem it has not proved.
Common mistakes
Acceptance by a strong test is the outcome most often misread.
Counterexample mode
Even a strong pass is not a primality certificate
Take and base nine. Since and , the initial chain value is . This base passes the strong condition even though the modulus is composite. The repaired conclusion is that rejection proves compositeness; acceptance for a particular base is not the converse of the prime theorem.
Common mistake
(Stopping a trial-division loop before the square-root boundary)
A trial-divisor loop must include the equality case . For the only prime divisor is and . A strict test stops at and wrongly declares prime. Excluding the boundary misses squares of primes.
Common mistake
(Reducing the exponent modulo the modulus)
Do not reduce an exponent modulo the value modulus. An exponent period needs a justified theorem and unit hypotheses, while repeated squaring needs no such reduction. Modulo , , but reducing the exponent modulo gives , which is wrong.
Counterexample mode
Two congruences need not have a common solution
Claim: any two congruences have a solution, unique modulo the product of the moduli. Take and . The first forces to be odd and the second forces to be even, so no integer satisfies both. Here does not divide . The repair: with , a solution exists exactly when divides the difference of the residues, and it is then unique modulo ; for coprime moduli and the stated theorem follows.
Summary
CRT merges exact local information using an inverse and a maintained period. Trial division gives a complete deterministic criterion with a square-root numerical cost. Strong compositeness witnesses exploit the prime-field square-root property and yield rigorous rejection; their acceptance status must be interpreted with the theorem's actual quantifiers.
Exercises
Quick check
(Apply the strong condition to with base 3, and obtain a factor if a nontrivial square root appears.)
Use .
Solution · Answer
Here , so . Since , , neither one nor ninety. There is no further tested index before , so this base rejects. Moreover , and yields a factor. The different outcome from base nine is consistent with a base-dependent necessary condition.
Quick check
(Solve and . Explain why uniqueness modulo the product fails.)
Use the linear-congruence theorem rather than an inverse that does not exist.
Solution · Answer
Write . The other condition gives , or , hence . Thus . The two distinct classes thirteen and forty-three modulo sixty both solve the original system. The moduli are not coprime; their lcm is thirty, so a product-modulus uniqueness claim would be false.
Quick check
(Explain why a trial-divisor loop must test 11 for . Then use the prime-divisor theorem to certify that 127 is prime.)
List every prime at most the relevant square root.
Solution · Answer
The composite has no prime divisor below eleven, so a strict inequality would miss its only prime factor. For , the prime candidates at most its square root are . Their respective remainders are , all nonzero. No prime factor at most the square root exists, so the theorem proves primality.