Function diophantine_all_soln

blockchain/diophantine_equation.py:33–71

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 -

(a: int, b: int, c: int, n: int = 2)

def 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

    """
    (x0, y0) = diophantine(a, b, c)  # Initial value
    d = greatest_common_divisor(a, b)
    p = a // d
    q = b // d

    for i in range(n):
        x = x0 + i * q
        y = y0 - i * p
        print(x, y)


def extended_gcd(a: int, b: int) -> tuple[int, int, int]: