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