# Number Theory¶

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

## Divisibility¶

 Finds the greatest common divisor of $$a$$ and $$b$$. Finds the multiplicands of $$a$$ and $$b$$ such that $$a s + b t = \mathrm{gcd}(a, b)$$. Computes the least common multiple of the arguments. 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$$. Determines if the arguments are pairwise coprime.

## Congruences¶

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

Last update: May 18, 2022