Divisibility testing by multiplication

Testing $d \mid n$ by computing $n \bmod d$ is wasteful when only a yes or no answer is needed. Granlund and Montgomery [GraMon1994, §9] observed that for odd $d$ the test reduces to a multiplication modulo $B = 2^{\mathtt{FLINT\_BITS}}$ . FLINT uses it for trial division in n_is_prime and n_factor, and exposes it as n_divisible_odd_gm.

Theorem 1. Let $d$ be odd, $d' = d^{-1} \bmod B$ and $L = \lfloor (B - 1)/d \rfloor$ . For $0 \le n < B$ ,

d \mid n \iff (n d' \bmod B) \le L.

Moreover, if $d \mid n$ then $n/d = n d' \bmod B$ .

Proof. Since $d'$ is odd, $\phi(n) = n d' \bmod B$ is a bijection of $\{0, 1, \ldots, B - 1\}$ . The multiples of $d$ in this range are $kd$ for $k = 0, 1, \ldots, L$ , and $\phi(kd) = k d d' \bmod B = k$ . So $\phi$ maps the $L + 1$ multiples of $d$ onto $\{0, \ldots, L\}$ . Being a bijection, it maps no other $n$ into this set. The second claim is $\phi(kd) = k$ .

For even $d = 2^e d_0$ , test that the lowest $e$ bits of $n$ are zero and that $d_0 \mid n$ .

Use in FLINT#

n_is_prime stores the pairs $(d', L)$ for the 34 odd primes from 3 to 149 in a table. For $n < 2^{32}$ the 32 tests after 3 and 5 are written as a branch-free loop, which compilers vectorise. Trial division in n_factor uses the same test, and when it succeeds divides out the prime with the exact quotient $n d' \bmod B$ from the theorem.

int n_divisible_odd_gm(ulong n, ulong inv1, ulong inv2)

int n_is_prime(ulong n)

void n_factor(n_factor_t * factors, ulong n, int proved)

@misc{flint-doc-algorithms-arithmetic-divisibility-test, author = {{The FLINT team}}, title = {{Divisibility testing by multiplication}}, howpublished = {FLINT: Fast Library for Number Theory, documentation, version 3.7.0-dev}, year = {2026}, url = {https://flintlib.org/doc/algorithms/arithmetic/divisibility-test.html}, note = {Generated 2026-11-02} }

Divisibility testing by multiplication

Use in FLINT#

Referenced from#

References#