Remainders keep repeated squaring inside a modulus.
Reducing after each multiplication preserves the modular result while repeated squaring shrinks the exponent, enabling one explicit fixed-base Fermat check.
What can one modular congruence establish about a candidate number, and what can it not establish?
- Reduce every squared or multiplied intermediate by the modulus
- Halve even exponents through repeated squaring
- Evaluate a fixed-base Fermat congruence for finite candidates
- Compare a passing congruence with trial-division classification
expmod follows the same exponent reduction as fast exponentiation, but applies remainder after every square or odd multiplication. The reduced result stays congruent to the unreduced power modulo modulus, so the final residue is preserved without carrying the full power.
passes-base-2? checks whether 2 raised to candidate is congruent to 2 modulo candidate. It passes for 17 and fails for 15. It also passes for 561 even though 561 equals 3 times 11 times 17. Each result records the exact base-2 congruence, while trial division supplies the composite classification.
- Output
- —
- Value
- —
- Diagnostic
- —
The modular power returns 3. The fixed-base checks return (#t #f #t) for 17, 15, and the composite 561.
Follow each even exponent into a half-size call before its residue is squared and reduced. In the second run, separate the three finite calls and observe that the returned booleans report the exact base-2 congruence.
Change the program and compare the result.
Add candidate 21 to the second program. Run the same base-2 check, then explain why a false result settles this congruence while a true result would still not prove primality.
Show hint
The test asks one exact equality. Passing that equality does not rule out composite numbers such as 561.