Diophantine Equation - Linear Diophantine Equations

Linear Diophantine Equations

For more details on this topic, see Bézout's identity.

Linear Diophantine equations take the form ax + by = c. If c is the greatest common divisor of a and b then this is Bézout's identity, and the equation has an infinite number of solutions. These can be found by applying the extended Euclidean algorithm. It follows that there are also infinitely many solutions if c is a multiple of the greatest common divisor of a and b. If c is not a multiple of the greatest common divisor of a and b, then the Diophantine equation ax + by = c has no solutions.