Linear Diophantine Equation

A Linear Diophantine Equation is an equation that has two or more integer variables and whose solutions are required to be integers.

The general form is:

ax + by = c

where:

a, b, c are given integers

x, y must also be integers

When does a solution exist? Before solving, we must check whether a solution is even possible.

Important Condition:

The equation ax + by = c

has an integer solution only if: gcd(a,b) ∣ c

meaning the Greatest Common Divisor of a and b must divide c

(x0, y0) is one solution, then all solutions are:

x = x0 + (b / gcd(a,b))t

y = y0 –  (a / gcd(a,b))t 

where t is any integer.

Example 1:

Find 30x + 18y = 6

Step 1: Find gcd(30,18) using the Euclidean Algorithm

The Euclidean Algorithm finds the gcd by repeated division.

30 ÷ 18 = 1 remainder 12

18 ÷ 12 = 1 remainder 6

12 ÷ 6 = 2 remainder 0

Since the remainder is now 0: gcd(30, 18) = 6

Step 2: Check the condition for solutions

We need: gcd(a, b) ∣ c

gcd(30, 18) | 6

Since: 6 | 6 the condition is satisfied, so integer solutions exist.

Step 3: Express the gcd as a combination of 30 and 18 (Back-substitution step)

Start from the second-to-last step

eq 1: 6 = 18 – 12

eq 2: 12 = 30 – 18

Replace 12 using the first equation

6 = 18 – 12

6 = 18 − (30 − 18)

Simplify:

6 = 18 − (30 − 18)

6 = 18 – 30 + 18

6 = (2 ◦ 18) – 30

Step 4: Match this with the original equation

We now have: −1 ◦ 30 + 2 ◦ 18 = 6   Compare this with the original equation:

Original Equation: 30x + 18y = 6

So one solution is: x = −1, y = 2 this is called a particular solution. (x0, y0)

Step 5: Find the general solution

A linear Diophantine equation does not have just one solution — it has infinitely many.

General solution formula

If: ax + by = c

and (x0, y0) is one solution, then all solutions are:

x = x0 + (b / gcd(a,b))t 

y = y0 – (a / gcd(a,b))t  

where t is any integer.

Apply the formula:

30x + 18y = 6

a = 30

b = 18

gcd = 6

x0 = −1, y0 = 2

x = x0 + (b / gcd(a,b))t

x = -1 + (18 / 6)t 

x = −1 + 3t

y = y0 – (a / gcd(a,b))t

y = 2 – (30 / 6)t 

y = 2 − 5t

Final answer: All integer solutions of: 30x + 18y = 6 are: x = −1 + 3t, y = 2 − 5t for t ∈ Z (t can be any integer)

Example 2:

Find 84x + 30y = 6

Step 1: Find gcd(84,30) using the Euclidean Algorithm

The Euclidean Algorithm finds the gcd by repeated division.

84 ÷ 30 = 2 remainder 24

30 ÷ 24 = 1 remainder 6

24 ÷ 6 = 4 remainder 0

Since the remainder is now 0: gcd(84, 30) = 6

Step 2: Check the condition for solutions

We need: gcd(84, 30) | 6

Since: 6 | 6  the condition is satisfied, so integer solutions exist.

Step 3: Express the gcd as a combination of 84 and 30 (Back-substitution step)

Start from the second-to-last step

eq 1: 6 = 30 – 24

eq 2: 24 = 84 – (30 ◦ 2)

Replace 24 using the first equation

6 = 30 – 24

6 = 30 − (84 − (30 ◦ 2))

Simplify:

6 = 30 − (84 − 30⋅2)

6 = 30 – 84 + (30 ⋅2)

6 = (30 ◦ 3) – 84

Step 4: Match this with the original equation

We now have: 84 ◦ -1 + 30 ◦ 3 = 6 Compare this with the original equation:

Original Equation: 84x + 30y = 6

So one solution is: x = −1, y = 3 this is called a particular solution. (x0, y0)

Step 5: Find the general solution

A linear Diophantine equation does not have just one solution — it has infinitely many.

General solution formula

If: ax + by = c and (x0, y0) is one solution, then all solutions are:

x = x0 + (b / gcd(a,b))t 

y = y0 – (a / gcd(a,b))t  

where t is any integer.

Apply the formula:

84x + 30y = 6

a = 84

b = 30

gcd = 6

x0 = −1, y0 = 3

x = x0 + (b / gcd(a,b))t 

x = -1 + (30 / 6)t

x = −1 + 5t

y = y0 – (a / gcd(a,b))t 

y = 3 – (84 / 6)t

y = 3 − 14t

Final answer: All integer solutions of: 84x + 30y = 6 are: x = −1 + 5t, y = 3 − 14t for t ∈ Z (t can be any integer)