Hacker's Delight

10-16. Test for Zero Remainder after Division by a Constant

The multiplicative inverse of a divisor d can be used to test for a zero remainder after division by d [GM].

Unsigned

First, consider unsigned division with the divisor d odd. Denote by d¯ the multiplicative inverse of d. Then, because dd¯ ≡ 1 (mod 2^W), where W is the machine’s word size in bits, d¯ is also odd. Thus, d¯ is relatively prime to 2^W, and as shown in the proof of theorem MI in the preceding section, as n ranges over all 2^W distinct values modulo 2^W, nd¯ takes on all 2^W distinct values modulo 2^W.

It was shown in the preceding section that if n is a multiple of d,

That is, ...