Motivation
The companion section defines the strong sequence, gives the exact algorithm and proves that prime inputs always pass. Here we fix an odd composite and prove a bound on the bases it fools. The point is to contain every passing base in one proper subgroup; the passing bases themselves need not form a subgroup. CRT handles moduli with distinct prime factors, while a small principal unit handles prime powers. As in the companion section, write with and odd; stage means the residue .
Theorem/proposition
Non-coprime bases
Lemma 8.3.1
(Non-coprime bases always fail)
Let be odd and let . Then for every . In particular fails, even if the gcd step is omitted.
Proof
(Reduce modulo the common factor)
Suppose with . Since , the same congruence holds modulo . But , so the left side is , and forces , a contradiction.
So every passing base is a unit modulo . We write , an abelian group of order , and
The half bound
Theorem 8.3.2
(The half bound)
Let be an odd composite number. Then the number of passing bases in satisfies
Hence a base drawn uniformly from passes with probability at most , which is strictly less than .
Quick check
(For , find the set of passing bases directly and compare with .)
Here , so and ; list the squares of the units first.
Solution · Answer
The units are , and their squares are only. Stage passes exactly , that is . Stage would need , and is not a square. Stage would need , but the squares of are . Hence and . The pass probability is , below one half as the theorem requires.
Proof sketch or proof idea
Proof
(A proper subgroup that contains every passing base)
Fix an odd composite with , odd, . Since , the residues and are distinct modulo , and is a subgroup of of order .
Step 1: choosing the stage . Let
The set contains , because gives for odd . So is nonempty and finite, and we let and put
By construction, there is a unit with . Also, no unit takes the value at any inspected stage with .
We do not need a separate case " is empty". The set always contains and , and in any case the argument below never uses that is nonempty. The stage is defined through the unit , whether or not other units reach .
Step 2: is a subgroup. Define by . Since is abelian, , so is a group homomorphism. Then
is the preimage of a subgroup under a homomorphism, hence a subgroup of .
Step 3: every passing base lies in . Let . There are two ways can pass.
- Case . Then , so .
- Case for some stage . Then , witnessed by , so by maximality. Write . If , this is . If , the exponent is even, and the value is . Either way .
This is the point at which the choice of as the last stage matters. A passing base reaches at stage or earlier, never later. Once a base has reached , every further squaring gives . So at stage all bases that passed at an earlier stage sit at , and those that pass exactly at stage sit at . The bases with are at throughout. The single subgroup captures all of them.
Step 4: is a proper subgroup. We must exhibit a unit with . Since is composite, exactly one of the following holds.
Case A: has at least two distinct prime factors. Choose a prime and let be the exact power of dividing . Put and . Then , and both and are odd and greater than , so both are at least . Let be the unit from Step 1 with . By CRT there is an integer with
Then is coprime to (because is) and to , so . Its -th power satisfies
If , reducing modulo gives , so . This is impossible since . If , reducing modulo gives , which is also impossible. Hence , and .
The image has mixed signs: on one coprime component and on the other. Such an element is a square root of modulo other than , which is exactly the kind of object a prime modulus cannot have.
Case B: with an odd prime and . Let . Since , is a unit. For every integer , the binomial theorem gives
because each term with is divisible by , and exactly when . Hence if and only if , that is, if and only if . So has order exactly .
Now . Indeed, is odd, so . Also and , so would give . Therefore . Moreover, , while since is odd. So either. Thus .
In Case B we did not use the specific value of , only that is coprime to . The prime-power case is easier in this respect.
Step 5: counting. is a proper subgroup of the finite group . By Lagrange's theorem, divides , and , so . By Step 3, .
Next, for composite . Among , every prime factor of satisfies and , so at least one element of is not a unit. By the non-coprime lemma, non-units contribute no passing bases. Hence
Dividing by the equally likely bases gives a pass probability of at most , which is strictly less than .
Proof X-ray
Where each hypothesis enters the half bound
Each hypothesis is used at one identifiable point. Oddness of gives , which makes nonempty, and it makes both CRT components in Case A at least , so an element with mixed signs cannot be . Compositeness is used only in Step 4. For a prime , neither case is available, and the conclusion genuinely fails: then , , and Euler's criterion puts every unit in , so . Commutativity of is used only to make a homomorphism.
The one non-obvious move is the choice , which must meet two opposing demands. Step 3 needs at least as large as every stage at which a passing base reaches . Case A of Step 4 needs a unit with at stage itself. A smaller index fails the first demand: the witness for passes, and with would square to , so escapes the smaller subgroup. A larger inspected index is not in , so it has no witness for Case A.
The argument closes by counting, not by describing . Step 3 gives only , and Lagrange's theorem bounds . Case B never looks at : its obstruction is an element of order , and because while .
Checking the edge cases
A proof with a case split and a carefully chosen index should be tested against small examples. Here is how each ingredient behaves for several odd composites.
Worked example 8.3.3
(The prime-power obstruction at )
. Here , so and . The squares of units mod are . Since is not a square, no unit reaches at stage or . So , , and . Case B applies with , and .
Worked example 8.3.4
(Mixed CRT signs at )
. Here , so the only inspected stage is and necessarily , . Case A applies with , , . CRT gives , since and . Then , so , which is not .
. Here and , and some units reach at stage . So , and the "earlier stages map to " part of Step 3 is used. See the exercise on a prime power with .
Worked example 8.3.5
(A subgroup containing more than the passing bases)
. Here , so and . A unit can reach at stage only if it does so both mod and mod . The -parts of and are both , so can occur at stage but not at stage or later. Indeed , so and .
- The roots of modulo are . For instance . So .
- The roots of are , where . So and .
- The CRT construction of Step 4 with , , gives , since and . Then , so . This has mixed signs, and , and is not .
- Note that . The bases and lie in but fail: for , and , so is a nontrivial square root of . The subgroup is a container for , not a description of it.
. This is the Carmichael number from the companion section. Mod , any even power of a unit is , so no unit reaches modulo at a stage . Hence and . Case A applies, for example with and . See the exercise on strong liars of a Carmichael number.
Two further remarks.
- If , then , and every element of passes at stage . So exactly. Strict containment can occur only when , as for .
- Case A does not require to be squarefree. For example, falls under Case A with and . Case B is used only when is a power of a single prime.
The theorem bounds one round. A full test repeats the round with fresh bases, and the bound then compounds.
Quick check
(An odd composite is tested with bases drawn independently and uniformly from . Bound the probability that all rounds pass.)
Use the theorem for one round and independence for the product.
Solution · Answer
Each round passes with probability at most, by the theorem, and that number is less than . The rounds are independent, so the probability that all pass is the product, at most . Independence is essential: reusing one base times gives no improvement over a single round.
Common mistakes
Common mistake
(Taking the last inspected stage instead of the last stage that reaches )
It is tempting to set outright. The set still contains every passing base, but it need not be proper. For we have , so . Since is a multiple of , and , every unit satisfies modulo , and , hence modulo . That subgroup is the whole group and bounds nothing. The proof uses the last stage at which some unit actually reaches ; that witness is what Case A needs.
Counterexample mode
The strong liars need not form a subgroup
A plausible claim is that the passing bases of a composite form a subgroup of , as the Fermat liars do (they are the kernel of ). For the worked example above found . Both and pass, but , so their product is . For we have and , so the round never meets and fails. Thus is not closed under multiplication. The correct statement is the one the proof uses: is contained in the subgroup , and only is counted by Lagrange's theorem.
Common mistake
(Reading the bound as the probability that a passing number is composite)
The theorem bounds the probability that a fixed composite passes, after independent rounds. It does not say that a number which passed rounds is composite with probability below . That reverse probability depends on how the input was chosen, for example on the proportion of primes among the candidates, and is computed with Bayes' rule.
Exercises
Quick check
(A prime power with : Let . You may use the fact that is cyclic of order and generated by .)
(a) Find and . Then determine the set of passing bases exactly, by solving the conditions of the strong-condition definition in the companion section in terms of exponents of the generator.
(b) Trace the round for the base .
(c) Determine , and as in the proof of the half bound. Verify that lies outside , both by direct computation and from the binomial formula .
(d) Explain how the two bases that pass at stage behave at stage .
Solution
(a) We have , so and . The round inspects for and , for . Write with taken modulo . Since , we have . Also , because .
- means , so . This gives .
- means , so . This gives .
- means , that is, . So , giving and . Indeed , and .
- means . Reducing modulo gives , so there is no solution.
Hence . The bases fail at the gcd step. So of the bases pass, within .
(b) For : , so , which is not . In the loop, gives . So , and the round passes at stage .
(c) Some unit, for example , reaches at stage , and none does at stage . So and . We compute .
- means , that is, , so and .
- was solved in (a), giving .
So , with , a subgroup of index . For : , , and . The binomial formula gives , in agreement. Since , we have . This uses , which holds because and is odd.
(d) The base stays at . The base is at at stage and becomes at stage . So at stage , the stage- bases sit at , and the stage- bases and sit at . All four lie in , exactly as Step 3 of the proof predicts.
Quick check
(Strong liars of a Carmichael number: Let , so and .)
(a) Show that no unit modulo satisfies for . Conclude that and .
(b) Count exactly using CRT and the fact that is cyclic of order .
(c) Compare with the bound and with the number of Fermat liars.
(d) Construct, as in Case A of the proof, an explicit unit using and , and compute .
Solution
(a) A unit modulo is a unit modulo , so . For the exponent is even, so . A value would reduce to , which is impossible since . So , and . Passing requires , and every such passes at stage . Hence .
(b) We have if and only if the congruence holds modulo , and . Count each component, using that in a cyclic group of order the equation has exactly solutions.
- Mod : , since is odd and . There is solution for each sign.
- Mod : , since . The equation has solutions. For , write for a generator . Then , and holds exactly for odd , giving solutions.
- Mod : , since . Because , the cube map is a bijection of the group, so each of has exactly preimage.
By CRT, has solutions, and also has . These sets are disjoint, so .
(c) , so the bound is , and . The pass probability is . By the companion section’s Carmichael-number example, all units are Fermat liars. The strong test thus reduces the liars from to .
(d) Use , which satisfies . We need and . Writing and using , we need . So and .
Then and . The integer satisfies the same two congruences, so . This is neither nor , so . Moreover : it is modulo and modulo . So is a nontrivial square root of , and .