Number Theory

This section contains functions for performing modular arithmetic and other number theoretic routines.

Divisibility

gcd(a, b)

Finds the greatest common divisor of \(a\) and \(b\).

egcd(a, b)

Finds the multiplicands of \(a\) and \(b\) such that \(a s + b t = \mathrm{gcd}(a, b)\).

lcm(*values)

Computes the least common multiple of the arguments.

prod(*values)

Computes the product of the arguments.

euler_phi(n)

Counts the positive integers (totatives) in \([1, n]\) that are coprime to \(n\).

totatives(n)

Returns the positive integers (totatives) in \([1, n]\) that are coprime to \(n\).

are_coprime(*values)

Determines if the arguments are pairwise coprime.

Congruences

pow(base, exponent, modulus)

Efficiently performs modular exponentiation.

crt(remainders, moduli)

Solves the simultaneous system of congruences for \(x\).

primitive_root(n[, start, stop, reverse])

Finds the smallest primitive root modulo \(n\).

primitive_roots(n[, start, stop, reverse])

Finds all primitive roots modulo \(n\).

carmichael_lambda(n)

Finds the smallest positive integer \(m\) such that \(a^m \equiv 1\ (\textrm{mod}\ n)\) for every integer \(a\) in \([1, n]\) that is coprime to \(n\).

legendre_symbol(a, p)

Computes the Legendre symbol \((\frac{a}{p})\).

jacobi_symbol(a, n)

Computes the Jacobi symbol \((\frac{a}{n})\).

kronecker_symbol(a, n)

Computes the Kronecker symbol \((\frac{a}{n})\).

is_primitive_root(g, n)

Determines if \(g\) is a primitive root modulo \(n\).

is_cyclic(n)

Determines whether the multiplicative group \((\mathbb{Z}/n\mathbb{Z}){^\times}\) is cyclic.

Integer arithmetic

isqrt(n)

Computes \(x = \lfloor\sqrt{n}\rfloor\) such that \(x^2 \le n < (x + 1)^2\).

iroot(n, k)

Computes \(x = \lfloor n^{\frac{1}{k}} \rfloor\) such that \(x^k \le n < (x + 1)^k\).

ilog(n, b)

Computes \(x = \lfloor\textrm{log}_b(n)\rfloor\) such that \(b^x \le n < b^{x + 1}\).