Concept
Theorem 2.5.4
Let odd prime satisfy with odd. Every nonzero satisfies , or for some .
- layman explanation: repeated squaring from the odd part must reach one through minus one unless it started at one.
If , Fermat gives . Choose the least with . Then
For odd composite , a base violating both alternatives is a strong witness; otherwise it is a strong liar.
Theorem 2.5.6
For composite , at most half of are strong liars.
- layman explanation: all bases that fool one round fit inside a proper subgroup, so they cannot occupy more than half the units.
If , every strong liar has order dividing both and , hence dividing ; thus it lies in . This subgroup is proper because
If has at least two prime-power factors, let be maximal with some and set . Every strong liar lies in . CRT chooses modulo one prime power and modulo the complementary factor, so is simultaneously and on different components and hence is neither . Thus is proper. In either case Lagrange gives size at most half.
Application
Independent rounds reduce the course bound to after rounds; 64 rounds give at most under this theorem.