Solving Linear Diophantine Equations for all integer solutions Using Python

What is a linear Diophantine Equation?

The simplest linear Diophantine equation takes the form

ax + by = d

, where

a

b

and

c

are given integers. The solutions are described by the following theorem:

This Diophantine equation has a solution (where

x

and

y

are integers) if and only if

c

is a multiple of the greatest common divisor of

a

and

b

. Moreover, if

(x, y)

is a solution, then the other solutions have the form

(x + kv, y - ku)

, where

k

is an arbitrary integer, and

u

and

v

are the quotients of

a

and

b

(respectively) by the greatest common divisor of

a

and

b

. (source: wiki)

To know whether a linear diophantine equation has integer solutions, we use the principles of Bézout's identity which states that in a linear diophantine equation ax+by=d, if a and b are nonzero integers and d their greatest common divisor,there exists integer solutions for both x and y.

Linear diophantine equations can be solved using substitution or more preferably Extended Euclidean Algorithm. Solving a linear diophantine equation is fairly easy by computer too. Here's a code in python that I made recently,the steps are described in the comments with the code.

Here's a sample output