Diophantine Equations
A Diophantine equation is an equation with multiple unknowns, where both the coefficients and solutions are integers. $$ ax+by=c $$
These equations are named after Diophantus of Alexandria.
A Practical Example
Consider the equation:
$$ 2x+6y=4 $$
Here, the coefficients are integers: a=2, b=6, c=4.
Similarly, the solutions x=-1 and y=1 are also integers.
Note: This equation has infinitely many solutions. For instance, x=5 and y=-1.
Identifying Diophantine Equations
Given three integer coefficients (a, b, c), there is no guarantee that the equation has integer solutions.
Example: This equation looks similar to the previous one but is not Diophantine since it has no integer solutions: $$ 2x+6y=3 $$
Even when integer solutions exist, they can sometimes be difficult to find.
Determining Whether an Equation Has Integer Solutions
A linear equation of the form ax + by = c has integer solutions (x, y) if and only if the greatest common divisor (GCD) of a and b divides c. $$ GCD(a,b)=d \quad \text{and} \quad d|c $$
Example
Consider the equation:
$$ 2x+6y=4 $$
The greatest common divisor of a and b is 2:
$$ GCD(2,6)=2 $$
Since 2 is a divisor of c=4, the equation has integer solutions and is therefore a Diophantine equation.
To find these solutions, we express GCD(a, b) as a linear combination of a and b:
$$ GCD(2,6) = 2 = j2 + k6 $$
One possible solution is j=-2 and k=1:
$$ (-2) \cdot 2 + 1 \cdot 6 = 2 $$
$$ -4 + 6 = 2 $$
Since integer solutions exist, there must be an integer $ h $ such that the general solutions are:
$$ x=jh = -2h $$
$$ y=kh = 1h $$
Substituting $ x=jh $ and $ y=kh $ into the equation $ 2x+6y=4 $ allows us to determine $ h $:
$$ 2(-2h) + 6(1h) = 4 $$
$$ -4h + 6h = 4 $$
$$ 2h = 4 $$
$$ h = 2 $$
Substituting $ h=2 $, we find the integer values of x and y:
$$ x= -2(2) = -4 $$
$$ y= 1(2) = 2 $$
Thus, one integer solution to the Diophantine equation $ 2x+6y=4 $ is $ x=-4 $ and $ y = 2 $:
$$ 2(-4) + 6(2) = 4 $$
$$ -8 + 12 = 4 $$
We have successfully found an integer solution.
Note: Finding the right integer $ h $ such that $ x=jh $ and $ y=kh $ is not always immediate.
Finding All Solutions to a Diophantine Equation
Once we have found one integer solution using the greatest common divisor GCD(a, b), we can generate all other solutions using the following formulas:
$$ x' = x - \frac{b}{d}n \\ y' = y + \frac{a}{d}n $$
where $ n $ is any integer.
Example
For the equation:
$$ 2x+6y=4 $$
We found one integer solution: x=-1 and y=1.
The greatest common divisor of a and b is 2:
$$ GCD(2,6)=2=d $$
Using the general formulas, all other integer solutions are:
$$ x' = x - \frac{b}{d}n = -1 - \frac{6}{2}n = -1 - 3n $$
$$ y' = y + \frac{a}{d}n = 1 + \frac{2}{2}n = 1 + n $$
By varying $ n $, we obtain an infinite set of integer solutions:
$$ \begin{array}{c|lcr} \text{n} & \text{x'} & \text{y'} \\ \hline 1 & -4 & 2 & \\ 2 & -7 & 3 & \\ 3 & -10 & 4 & \end{array} $$
And so on.
