Would someone mind elaborating the explanation in the manual?

David McKen cic_3_b at yahoo.com
Fri Oct 24 21:42:39 CEST 2003

In the efficiency section of the GMP manual I came across the
following couple lines

--Begin quote--
However when testing divisibility by several small integers, it's
best to take a remainder modulo their product, to save
multi-precision operations. For instance to test whether a number is
divisible by any of 23, 29 or 31 take a remainder modulo 23*29*31 =
20677 and then test that.
--End quote--

Needless to say I don't understand this. Does someone have either a
web site that has the formulas describing this process (also if
possible a proof) or some example code that achieves this purpose?

I have already searched google and I keep coming up with the disible
"tricks" these only show divisibility for one number. I am interested
in checking if a number is divisible by a couple small numbers (to
weed out values before I waste time doing detailed computation)

Thanks in Advance

David Mcken

Life Sucks
Live with it

Do you Yahoo!?
The New Yahoo! Shopping - with improved product search

More information about the gmp-discuss mailing list