Diophantus of Alexandria was a major Greek mathematician, yet little is known about him (see the article "Diophantus of Alexandria, the great unknown"). He established the rule of signs for operations on negative numbers, although he described them as "absurd". But his principal legacy is the adjective "Diophantine", which applies to any polynomial equation whose coefficients and solutions are integers. One of the most elementary Diophantine equations imaginable is undoubtedly ax + by = c, with unknowns x and y (where the integers a, b and c are given). Simple though it is, it has found a wealth of applications.
The Bachet–Bézout theorem
----------------------------
First, note that the greatest common divisor of a and b, denoted by d = gcd (a, b), divides a and b by definition, and therefore divides the left-hand side ax + by of our equation. If the right-hand side c is not divisible by d, there can clearly be no solution. Otherwise, Bachet was the first to show that the equation has at least one solution. The result was long attributed to Étienne Bézout before being more appropriately named the Bachet–Bézout theorem.
Let us first consider the equation ax + by = 1, where the coefficients a and b are coprime (that is, d = 1). The general solution can be obtained from any particular solution (x0, y0), since
a ( x*0 ‒ kb) + b ( y*0 + ka) = ax0 + by 0 = 1 for every integer k.
The challenge, then, is to find such a particular solution (x0, y0), either by trial and error or, more efficiently, by the Euclidean algorithm or by using congruences.
