# Number theory¶

At the bottom level of the package hierarchy are various helper functions which implement standard number-theoretic algorithms.

thompson.number_theory.gcd(a, b)[source]

Calculate the Greatest Common Divisor of a and b.

Unless b==0, the result will have the same sign as b (so that when b is divided by it, the result comes out positive).

>>> gcd(12, 8)
4
>>> gcd(0, 50)
50
>>> gcd(7, 101)
1

thompson.number_theory.extended_gcd(a, b)[source]

From this exposition of the extended gcd algorithm. Computes $$d = \gcd(a, b)$$ and returns a triple $$(d, x, y)$$ where $$d = ax + by$$.

>>> extended_gcd(14, 33)
(1, -7, 3)
>>> extended_gcd(12, 32)
(4, 3, -1)

thompson.number_theory.lcm(*args)[source]

Computes the least common multiple of the given args. If a single argument is provided, the least common multiple of its elements is computed.

>>> n = randint(1, 1000000)
>>> lcm(n) == n
True
>>> lcm(2, 13)
26
>>> lcm(*range(1, 10)) #1, 2, ..., 9
2520
>>> lcm(range(1, 10))  #Don't have to unpack the arguments
2520

thompson.number_theory.solve_linear_diophantine(a, b, c)[source]

Solves the equation $$ax + by = c$$ for integers $$x, y \in\mathbb{Z}$$.

Return type: None if no solution exists; otherwise a triple (base, inc, lcm) where base is a single solution $$(x_0, y_0)$$; inc is a pair $$(\delta x, \delta y)$$ such that if $$(x, y)$$ is a solution, so is $$(x, y) \pm (\delta x, \delta y)$$; and lcm is the value of $$\operatorname{lcm}(a, b)$$.
thompson.number_theory.solve_linear_congruence(a, b, n)[source]

Solves the congruence $$ax \equiv b \pmod n$$.

Return type: a SolutionSet representing all such solutions $$x$$.
>>> x = solve_linear_congruence(6, 12, 18)
>>> print(x)
{..., -1, 2, 5, 8, 11, 14, ...}
>>> y = solve_linear_congruence(5, 7, 11)
>>> print(y)
{..., -3, 8, 19, 30, 41, 52, ...}
>>> print(x & y)
{..., -25, 8, 41, 74, 107, 140, ...}

thompson.number_theory.divisors(n, include_one=True)[source]

An iterator that yields the positive divisors $$d \mid n$$.

Parameters: include_one (bool) – set to False to exlude $$d = 1$$.
>>> list(divisors(12))
[1, 2, 3, 4, 6, 12]
>>> list(divisors(125, include_one=False))
[5, 25, 125]

thompson.number_theory.prod(iterable)[source]

Handy function for computing the product of an iterable collection of numbers. From Stack Overflow.

>>> prod(range(1, 5))
24