Linear Diophantine Equations

Welcome, students 👋 In this lesson, you will learn how to solve linear Diophantine equations, which are equations where we look for integer solutions only. These ideas matter because many real-world counting problems, packing problems, and “can this be done exactly?” questions turn into this kind of number theory challenge.

What you will learn

By the end of this lesson, you should be able to:

explain what a linear Diophantine equation is
use key ideas like the greatest common divisor, or $\gcd$
decide whether an equation has integer solutions
find all integer solutions when they exist
see how these equations fit into the larger study of Diophantine equations 📘

A big idea to remember is this: in algebra, we often want real-number solutions, but in number theory, we often care about whole-number or integer solutions. That change makes the problem very different and very interesting.

What is a linear Diophantine equation?

A linear Diophantine equation is an equation of the form

$$ax + by = c$$

where $a$, $b$, and $c$ are integers, and we want $x$ and $y$ to be integers too.

The word linear means the variables appear only to the first power, like $x$ and $y$, not $x^2$ or $xy$. The word Diophantine refers to equations studied in integers.

For example:

$3x + 5y = 11$
$7x - 4y = 1$
$12x + 18y = 6$

Each of these is linear because the variables are not squared or multiplied together.

A key point is that not every linear equation has integer solutions. For example, $2x + 4y = 7$ has no integer solutions because the left side is always even, while $7$ is odd. This is a structural reason: the equation fails because of how integers behave, not because we did not try hard enough. 🔎

The main test for whether solutions exist

The most important fact about linear Diophantine equations is this:

An equation of the form $ax + by = c$ has integer solutions if and only if $\gcd(a,b)$ divides $c$.

Here, $\gcd(a,b)$ means the greatest common divisor of $a$ and $b$.

Why this matters

Suppose $d = \gcd(a,b)$. Then both $a$ and $b$ are multiples of $d$, so the expression $ax + by$ must also be a multiple of $d$ for any integers $x$ and $y$. That means the right side $c$ must also be a multiple of $d$.

So if $d$ does not divide $c$, there are no integer solutions.

Example 1: no solution

Consider

$$6x + 10y = 7$$

We find

$$\gcd(6,10) = 2$$

But $2$ does not divide $7$. Therefore, this equation has no integer solutions.

Example 2: solution exists

Consider

$$6x + 10y = 8$$

Again,

$$\gcd(6,10) = 2$$

and $2$ divides $8$, so integer solutions do exist.

This test gives us a fast way to check whether a problem is worth solving further. ✅

Finding one integer solution

Once we know solutions exist, the next goal is often to find one specific integer solution. After that, we can generate all others.

Let’s solve

$$3x + 5y = 11$$

We want integers $x$ and $y$.

Try values that make the equation easier. If $y = 1$, then

$$3x + 5 = 11$$

$$3x = 6$$

and

$$x = 2$$

So one integer solution is

$$(x,y) = (2,1)$$

This is a valid solution because

$$3(2) + 5(1) = 11$$

In simple problems, guessing can work. But for harder equations, we need a more systematic method.

A systematic method using the Euclidean algorithm

The Euclidean algorithm helps us compute $\gcd(a,b)$ efficiently. It also helps us find one solution to $ax + by = c$ when one exists.

Let’s solve

$$12x + 18y = 6$$

First, compute the gcd:

$$\gcd(12,18) = 6$$

Since $6$ divides $6$, solutions exist.

Now divide the whole equation by $6$:

$$2x + 3y = 1$$

Now we look for integers $x$ and $y$.

If $y = -1$, then

$$2x - 3 = 1$$

$$2x = 4$$

which gives

$$x = 2$$

So one solution is

$$(x,y) = (2,-1)$$

Check:

$$12(2) + 18(-1) = 24 - 18 = 6$$

This method works because dividing by the gcd simplifies the equation to a smaller, equivalent problem.

The structure of all integer solutions

A powerful fact about linear Diophantine equations is that once you know one solution, you can describe every solution.

If $ax + by = c$ has one integer solution $(x_0,y_0)$, and $d = \gcd(a,b)$, then all integer solutions are given by

$$x = x_0 + \frac{b}{d}t$$

$$y = y_0 - \frac{a}{d}t$$

for any integer $t$.

This formula is very important because it shows that solutions come in a whole family, not just one pair.

Example 3: all solutions

We already found one solution to

$$2x + 3y = 1$$

which is $(2,-1)$.

Here, $a = 2$, $b = 3$, and $d = \gcd(2,3) = 1$.

So all solutions are

$$x = 2 + 3t$$

$$y = -1 - 2t$$

for any integer $t$.

Check it:

$$2(2 + 3t) + 3(-1 - 2t) = 4 + 6t - 3 - 6t = 1$$

The $t$ terms cancel, which shows every pair generated this way is a solution.

This is a major structural idea in number theory: changing one variable by a certain amount forces the other to change in a matching way so the equation stays true. 🔁

Why the solution set forms a pattern

The formula for all solutions is not random. It comes from the fact that if $(x_0,y_0)$ is one solution, then any other solution $(x,y)$ must satisfy

$$a(x-x_0) + b(y-y_0) = 0$$

Rearranging gives

$$a(x-x_0) = -b(y-y_0)$$

So the difference between two solutions must balance perfectly. Because $a$ and $b$ share a gcd, the changes in $x$ and $y$ must happen in steps based on $\frac{b}{d}$ and $\frac{a}{d}$.

This is a strong example of structural reasoning: instead of checking every possible integer pair, we use the equation’s form to understand the whole solution set.

Real-world style examples

Linear Diophantine equations often appear in counting and combination problems.

Example 4: coins

Suppose a jar contains only $2$-cent and $5$-cent coins, and the total value is $11$ cents. Let $x$ be the number of $2$-cent coins and $y$ be the number of $5$-cent coins. Then

$$2x + 5y = 11$$

We want nonnegative integer solutions.

Try $y = 1$:

$$2x + 5 = 11$$

$$x = 3$$

This gives $(x,y) = (3,1)$.

Try $y = 3$:

$$2x + 15 = 11$$

which is impossible for nonnegative $x$.

From the general solution, if one solution is $(3,1)$ and $d = 1$, then

$$x = 3 + 5t$$

$$y = 1 - 2t$$

To keep both values nonnegative, only certain integers $t$ are allowed.

This shows an important idea: a linear Diophantine equation may have infinitely many integer solutions, but only a few may be useful in a real-world setting because we often require nonnegative values.

Connection to Diophantine Equations I

Linear Diophantine equations are often the first major type studied in Diophantine Equations I because they introduce the main style of reasoning used in the topic.

They teach you to:

focus on integer solutions only
use divisibility and gcd ideas
reason about structure instead of only calculation
describe whole families of solutions

These skills prepare you for harder Diophantine problems later, where equations may be nonlinear, more complicated, or require clever modular reasoning.

In other words, linear Diophantine equations are a training ground for number theory thinking. They show how arithmetic properties like divisibility can completely control whether solutions exist.

Conclusion

Linear Diophantine equations are equations of the form $ax + by = c$ where we want integer solutions. The key test is whether $\gcd(a,b)$ divides $c$. If it does, at least one integer solution exists; if it does not, no integer solution exists. Once one solution is found, all solutions can be written in a clear pattern using an integer parameter. This makes the topic a perfect example of structural reasoning in number theory. students, when you study these equations, you are learning how to use divisibility, pattern recognition, and algebra together to solve integer problems. 🌟

Study Notes

A linear Diophantine equation has the form $ax + by = c$ with integers $a$, $b$, and $c$.
We seek integer values of $x$ and $y$.
The equation has integer solutions if and only if $\gcd(a,b)$ divides $c$.
If $\gcd(a,b)$ does not divide $c$, there are no integer solutions.
If one solution $(x_0,y_0)$ exists, then all solutions are

$$x = x_0 + \frac{b}{d}t$$

$$y = y_0 - \frac{a}{d}t$$

where $d = \gcd(a,b)$ and $t$ is any integer.

The Euclidean algorithm is useful for finding $\gcd(a,b)$ and helping solve equations.
Structural reasoning means using the equation’s arithmetic pattern to understand all solutions.
Nonnegative integer solutions are important in applications like coins, tickets, and packing problems.
Linear Diophantine equations are an important starting point in Diophantine Equations I.