There's a way for odd divisors, since they have a multiplicative inverse mod 2^n. For example, the inverse of 3 modulo 2^32 is 0xAAAAAAAB. If you multiply an

There's a way for odd divisors, since they have a multiplicative inverse mod 2^n. For example, the inverse of 3 modulo 2^32 is 0xAAAAAAAB. If you multiply an unsigned number x by 0xAAAAAAAB, the result is less than or equal to 0xFFFFFFFF/3 if and only x is divisible by 3. Of course this is only possible for non-bignum computations. But there are other tricks for bignums, for example the number of even set bits in a multiple of three is equal to the number of odd set bits, because 4*n+k = n+k (mod 3) and the property is true for 0 and 3 but not 1 and 2.