Linear Diophantine Equations

 

Linear Diophantine equations are equations of the form:

$$ax+by=c$$

where $a, b, c, x,$ and $y$ are integers, and $a, b$ are not both zero.

These equations are named after the ancient Greek mathematician Diophantus, who studied them extensively. The solutions to these equations are integers $x$ and $y$ that satisfy the equation.

Linear Diophantine equations have applications in various fields, including number theory, cryptography, and optimization problems.

A Diophantine equation is a polynomial equation with 2 or more integer unknowns.

A Linear Diophantine equation (LDE) is an equation with 2 or more integer unknowns and the integer unknowns are each to at most degree of 1.

Linear Diophantine equation in two variables takes the form of $𝑎𝑥+𝑏𝑦=𝑐$, where $𝑥,𝑦∈ℤ$ and $a, b, c$ are integer constants. $x$ and $y$ are unknown variables.

A Homogeneous Linear Diophantine equation (HLDE) is $𝑎𝑥+𝑏𝑦=0$,$x,y∈Z$. Note that $x=0$ and $𝑦=0$is a solution, called the trivial solution for this equation.

Here's how you can solve Linear Diophantine Equations:

Check for Solutions: First, you need to determine if there are any solutions at all. This involves checking if $c$ is divisible by the greatest common divisor (GCD) of $a$ and $b$. If it is, then solutions are possible; otherwise, there are no integer solutions.

Find One Solution: You can use the Extended Euclidean Algorithm to find one solution to the equation. The algorithm gives you values of $x$ and $y$ such that $ax + by = \text{GCD}(a, b)$

Find All Solutions: Once you have one solution, you can find all solutions by adding integer multiples of $b/\text{GCD}(a, b)$ to the $x$ value and subtracting integer multiples of $a/\text{GCD}(a, b)$ from the $y$ value. This will give you all possible solutions.

• The general solution can be expressed as: $x = x_0 + \frac{b}{\gcd(a, b)}t$, $y = y_0 - \frac{a}{\gcd(a, b)}t$.
• Here, $(x_0) and (y_0)$ are the initial solutions, and $(t)$ is an integer parameter.

Special Cases:If $a$ and $b$ are relatively prime (i.e., their GCD is 1), then there are infinitely many solutions.If $c$ is not divisible by the GCD of $a$ and $b$, then there are no integer solutions.

So follow these steps to find the solutions of linear Diophantine equation $ax+by=c$

• Calculate $d=gcd(a,b)$ using the Euclid's Algorithm
• Check whether $d$ divides $c$:if it does not, there are no solutions, stop here.If it does write $c=de$
• If $d|c$ , find integers $u$ and $v$ such that $au+bu=d$, then $x_0=ue,y_0=ve$ is a particular solution of $ax+by=c$

Now find the general solution $x,y$ of the equation using the formauls

$$x=x_0+\frac{b}{d}. t\: ,t \in \mathbb{Z}$$ $$y_0=y_0-\frac{a}{d}.t \: ,t \in \mathbb{Z}$$

Let's illustrate with an example:

Example: Solve the linear Diophantine equation $15x+25y=10$

Check for Solutions: The GCD of 15 and 25 is 5. Since 10 is divisible by 5, solutions are possible.

Find One Solution: 

Using the Extended Euclidean Algorithm, we find that $15 \times (-1) + 25 \times (1) = 10$. So, one solution is $x=-1$ and $y=1$ 

Find All Solutions: 

Adding integer multiples of $25/5=5$ to -1 and subtracting integer multiples of  $15/5=3$ from 1, we get all possible solutions. So, the general solution is $x=-1+5t$ and $y=1−3t$, where $t$ is an integer

Homogeneous Linear Diophantine Equation

Let $𝑎𝑥+𝑏𝑦=0,𝑥,𝑦∈ℤ$ be a homogeneous linear Diophantine equation.
If $gcd(𝑎,𝑏)=𝑑$ then the complete family of solutions to the above equation is
$𝑥=\frac{𝑏}{𝑑}t$, and $𝑦=\frac{−𝑎}{𝑑}t,t∈Z.$

Example:Solve the Homogeneous linear Diophantine equation

$6𝑥+9𝑦=0,𝑥,𝑦∈ℤ$

Solution:
Note that GCD of 6 and 9 is 3. Hence the solutions are
$𝑥=\frac{9}{3}t$ and $𝑦=\frac{−6}{3}t, t∈Z$.