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
- Distinguish a passing congruence from a primality proof
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. A failure rejects this congruence, but one passing base is evidence only and is not a proof that the candidate is prime.
(begin
(define (square value) (* value value))
(define (expmod base exponent modulus)
(cond ((= exponent 0) 1)
((even? exponent)
(remainder (square (expmod base (/ exponent 2) modulus))
modulus))
(else
(remainder (* base (expmod base (- exponent 1) modulus))
modulus))))
(expmod 7 128 13))- 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 only the base-2 congruence. They do not authenticate primality.
Change the program before you read the hint.
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 one hint
The test asks one exact equality. Passing that equality does not rule out composite numbers such as 561.