# 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. Counts the positive integers (totatives) in $$[1, n]$$ that are coprime to $$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$$. 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$$. Computes the Legendre symbol $$(\frac{a}{p})$$. jacobi_symbol(a, n) Computes the Jacobi symbol $$(\frac{a}{n})$$. Computes the Kronecker symbol $$(\frac{a}{n})$$. Determines if $$g$$ is a primitive root modulo $$n$$. Determines whether the multiplicative group $$(\mathbb{Z}/n\mathbb{Z}){^\times}$$ is cyclic.

## Integer arithmetic¶

 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}$$.