Number Theory

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

Divisibility

gcd()

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

egcd()

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

lcm()

Computes the least common multiple of the arguments.

prod()

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()

Determines if the arguments are pairwise coprime.

Congruences

crt()

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

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

Finds a primitive root modulo \(n\) in the range [start, stop).

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

Iterates through all primitive roots modulo \(n\) in the range [start, stop).

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}\).
Last update: Apr 25, 2022