Introduction

A linear Diophantine equation has the form ax + by = c, where a, b, and c are integers and the goal is to find integer values of x and y. The problem is simple to state, but the solution depends on one precise condition involving the greatest common divisor.

The standard tool is the extended Euclidean algorithm. Once you know one solution, you automatically know all integer solutions.

Check Whether a Solution Exists

The equation

ax + by = c

has an integer solution if and only if gcd(a, b) divides c.

That is the first thing to test. If gcd(a, b) does not divide c, stop immediately because no integer solution exists.

For example:

• '6x + 9y = 12 has solutions because gcd(6, 9) = 3 and 3 divides 12'
• '6x + 9y = 10 has no solutions because 3 does not divide 10'

Use the Extended Euclidean Algorithm

The extended Euclidean algorithm finds integers s and t such that:

as + bt = gcd(a, b)

Once you have those coefficients, scale them by c / gcd(a, b) to get one particular solution to ax + by = c.

Here is a compact Python implementation:

1def extended_gcd(a, b):
2    if b == 0:
3        return abs(a), 1 if a > 0 else -1, 0
4
5    g, x1, y1 = extended_gcd(b, a % b)
6    x = y1
7    y = x1 - (a // b) * y1
8    return g, x, y
9
10
11def solve_linear_diophantine(a, b, c):
12    g, xg, yg = extended_gcd(a, b)
13
14    if c % g != 0:
15        return None
16
17    scale = c // g
18    x0 = xg * scale
19    y0 = yg * scale
20    return g, x0, y0
21
22
23print(solve_linear_diophantine(6, 9, 12))

This returns one valid integer pair together with the gcd.

Describe All Integer Solutions

If (x0, y0) is one solution and g = gcd(a, b), then every integer solution is:

x = x0 + (b / g) * k
y = y0 - (a / g) * k

where k is any integer.

That formula matters because Diophantine equations usually have either no solutions or infinitely many integer solutions.

Worked Example

Solve:

6x + 9y = 12

First, gcd(6, 9) = 3, and 3 divides 12, so solutions exist.

One relation from the extended Euclidean algorithm is:

6(-1) + 9(1) = 3

Multiply both sides by 4:

6(-4) + 9(4) = 12

So one particular solution is:

x0 = -4
y0 = 4

Now apply the general formula:

x = -4 + 3k
y = 4 - 2k

for any integer k.

When You Need Positive Solutions

Sometimes the problem asks for non-negative or positive solutions only. In that case, the general solution is still the right starting point, but you must choose k so both variables land in the required range.

That turns the problem into a small inequality exercise instead of a new number-theory method.

Common Pitfalls

• Forgetting to check whether gcd(a, b) divides c before searching for solutions.
• Finding one solution and stopping even though the full family of solutions is required.
• Mixing up the signs in the general solution formula.
• Assuming every Diophantine equation has a positive solution just because it has an integer solution.
• Trying random substitutions instead of using the extended Euclidean algorithm directly.

Summary

• A linear Diophantine equation ax + by = c has integer solutions exactly when gcd(a, b) divides c.
• The extended Euclidean algorithm gives one particular solution efficiently.
• Once one solution is known, all solutions follow from a simple parameter k.
• For restricted solutions such as non-negative integers, apply inequalities to the general form.
• The key step is arithmetic structure, not brute-force searching.