Linear Diophantine Equation

Linear Diophantine Equation

A linear Diophantine equation is an equation of the form

where $a$, $b$, and $c$ are given integers, and we seek integer solutions $x, y \in \mathbb{Z}$.

When Does a Solution Exist?

Let $d = \gcd(a, b)$. The equation $ax + by = c$ has an integer solution if and only if

that is, $d$ divides $c$ exactly.

This follows from Bézout's identity, which guarantees integers $x_0, y_0$ such that

If $d \mid c$, scaling both sides by $c/d$ gives a solution to the original equation.

Finding a Particular Solution

The extended Euclidean algorithm computes $\gcd(a, b)$ while also producing $x_0, y_0$ satisfying $a x_0 + b y_0 = d$. Multiplying through by $c/d$ gives one particular solution:

def extended_gcd(a, b):
    if b == 0:
        return a, 1, 0  # base case: gcd(a, 0) = a, with a*1 + 0*0 = a
    d, x1, y1 = extended_gcd(b, a % b)
    # back-substitute the smaller pair's coefficients to get x, y for (a, b)
    x, y = y1, x1 - (a // b) * y1
    return d, x, y

def solve_linear_diophantine(a, b, c):
    d, x0, y0 = extended_gcd(a, b)
    if c % d != 0:
        return None  # d does not divide c, so no integer solution exists
    scale = c // d
    # a*x0 + b*y0 = d, so scaling both sides by c/d gives a*x + b*y = c
    return x0 * scale, y0 * scale

print(solve_linear_diophantine(6, 15, 9))  # e.g. (-6, 3)

The General Solution

Once one particular solution $(x_1, y_1)$ is known, every integer solution has the form

This describes an infinite family of solutions spaced along a line with integer step size $\left(\frac{b}{d}, -\frac{a}{d}\right)$.

Worked Example

Solve $6x + 15y = 9$.

• $d = \gcd(6, 15) = 3$, and $3 \mid 9$, so solutions exist.
• Extended Euclidean algorithm gives $6(-2) + 15(1) = 3$, so $x_0 = -2,\ y_0 = 1$.
• Scale by $c/d = 9/3 = 3$: particular solution $x_1 = -6,\ y_1 = 3$.
• General solution: $$x = -6 + 5t, \qquad y = 3 - 2t, \qquad t \in \mathbb{Z}$$

Check $t = 1$: $x = -1, y = 1 \implies 6(-1) + 15(1) = 9$. ✅

Why It Matters

Linear Diophantine equations underpin many areas of number theory and computer science:

• Modular arithmetic — solving $ax \equiv c \pmod{b}$ reduces to a linear Diophantine equation.
• Cryptography — computing modular inverses (e.g., in RSA) uses the extended Euclidean algorithm.
• Scheduling / tiling problems — finding integer combinations of two step sizes that reach a target value.

Reference

• https://en.wikipedia.org/wiki/Diophantine_equation
• https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm