Would someone mind elaborating the explanation in the manual?

[Kevin Ryde]

Sisyphus <kalinabears at iinet.net.au> writes:
>
> the number of
> small integers for which divisibility needs to be tested.

On some chips gcc "%" operator isn't very fast unfortunately.  (Alpha
is a bit notorious in this respect.)  If it's a constant divisor you
can re-write it as a mul-by-inverse though.

> I've also seen literature (not specifically relating to GMP)
> suggesting that you could simply calculate the gcd of bignum and 20677
> - or you could extend that to calculating the gcd of R and 20677.

Usually a gcd is slower than a division.  But as it happens gcd_1 uses
the faster "modexact" style remainder (which unfortunately is not made
available for direct application use) and for big enough numbers might
be a net gain.