Module modular 

Modular arithmetic and the Euclidean algorithms — the backbone the rest of the library (primality, totient, CRT) is built on. Overflow-safe via u128/i128 intermediates.

Functions

crt

Chinese Remainder: solve x ≡ r1 (mod m1), x ≡ r2 (mod m2) for coprime moduli, returning (x, m1·m2). None if the moduli are not coprime.

extended_gcd

Extended Euclid: returns (g, x, y) with a·x + b·y = g = gcd(a, b).

gcd

Greatest common divisor (binary/Euclid). gcd(0, n) = n.

lcm

Least common multiple. 0 if either argument is 0.

mod_inverse

Modular multiplicative inverse of a mod m: the x with a·x ≡ 1 (mod m). None when gcd(a, m) ≠ 1 (no inverse exists) — fail closed.

mod_pow

(base^exp) mod modulus by repeated squaring. modulus = 0 → 0 (degenerate).