blockchain.diophantine_equation

Functions

all_diophantine_solutions(→ list[tuple[int, int]])	Return up to n integer solutions (x, y) to the linear Diophantine equation
diophantine(→ tuple[float, float])	Diophantine Equation : Given integers a,b,c ( at least one of a and b != 0), the
diophantine_all_soln(→ None)	Lemma : if n|ab and gcd(a,n) = 1, then n|b.
extended_gcd(→ tuple[int, int, int])	Extended Euclid's Algorithm : If d divides a and b and d = a*x + b*y for integers

Module Contents

blockchain.diophantine_equation.all_diophantine_solutions(a: int, b: int, c: int, n: int = 2) → list[tuple[int, int]]

Return up to n integer solutions (x, y) to the linear Diophantine equation a*x + b*y = c using the extended Euclidean algorithm.

Raises

ValueError

If no integer solutions exist.

Time complexity

O(log(max(|a|, |b|))) to compute a base solution using extended_gcd; plus O(n) to enumerate n solutions.

Space complexity

O(1) beyond the returned list.

Examples

>>> all_diophantine_solutions(10, 6, 14, n=2)
[(-7, 14), (-4, 9)]
>>> all_diophantine_solutions(10, 6, 14, n=4)
[(-7, 14), (-4, 9), (-1, 4), (2, -1)]
>>> all_diophantine_solutions(3, 6, 10, n=1)
Traceback (most recent call last):
...
ValueError: No integer solutions exist for a=3, b=6, c=10

blockchain.diophantine_equation.diophantine(a: int, b: int, c: int) → tuple[float, float]

Diophantine Equation : Given integers a,b,c ( at least one of a and b != 0), the diophantine equation a*x + b*y = c has a solution (where x and y are integers) iff greatest_common_divisor(a,b) divides c.

GCD ( Greatest Common Divisor ) or HCF ( Highest Common Factor )

>>> diophantine(10,6,14)
(-7.0, 14.0)

>>> diophantine(391,299,-69)
(9.0, -12.0)

But above equation has one more solution i.e., x = -4, y = 5. That’s why we need diophantine all solution function.

blockchain.diophantine_equation.diophantine_all_soln(a: int, b: int, c: int, n: int = 2) → None

Lemma : if n|ab and gcd(a,n) = 1, then n|b.

Finding All solutions of Diophantine Equations:

Theorem : Let gcd(a,b) = d, a = d*p, b = d*q. If (x0,y0) is a solution of Diophantine Equation a*x + b*y = c. a*x0 + b*y0 = c, then all the solutions have the form a(x0 + t*q) + b(y0 - t*p) = c, where t is an arbitrary integer.

n is the number of solution you want, n = 2 by default

>>> diophantine_all_soln(10, 6, 14)
-7.0 14.0
-4.0 9.0

>>> diophantine_all_soln(10, 6, 14, 4)
-7.0 14.0
-4.0 9.0
-1.0 4.0
2.0 -1.0

>>> diophantine_all_soln(391, 299, -69, n = 4)
9.0 -12.0
22.0 -29.0
35.0 -46.0
48.0 -63.0

blockchain.diophantine_equation.extended_gcd(a: int, b: int) → tuple[int, int, int]

Extended Euclid’s Algorithm : If d divides a and b and d = a*x + b*y for integers x and y, then d = gcd(a,b)

>>> extended_gcd(10, 6)
(2, -1, 2)

>>> extended_gcd(7, 5)
(1, -2, 3)