FLINT3.7.0-dev
/

nmod_divides

Synopsis#include <flint/nmod.h>
int nmod_divides(ulong * a, ulong b, ulong c, nmod_t mod)source

If ac \equiv b \pmod n has a solution, sets *a to one solution and returns 1; otherwise returns 0. Unlike nmod_div, this works when c is not invertible. Requires reduced b and c.

The congruence ac \equiv b \pmod n is solvable if and only if g = \gcd(c, n) divides b, and then it has exactly g solutions modulo n. nmod_divides computes u with u c \equiv g \pmod n by the extended Euclidean algorithm and returns a = (b/g)\, u \bmod n, which is not necessarily the least solution. If c = 0, then *a is set to 0, and the return value is 1 if b = 0 and 0 otherwise. When there is no solution and c \ne 0, *a is not modified.

Guides#

Cite this page

The FLINT team, “nmod_divides (nmod.h),” FLINT: Fast Library for Number Theory, documentation, version 3.7.0-dev, 2026. https://flintlib.org/doc/nmod/nmod_divides.html (generated 2026-10-20).