Diophantine Equations

The Central Idea

A Diophantine equation is an equation for which the variables are required to take integer values.

A basic linear Diophantine equation has the form

where \(a\), \(b\), and \(c\) are integers and the unknowns \(x\) and \(y\) must also be integers.

A First Example

Consider

One integer solution is

because

Therefore,

is an integer solution.

Real Solutions Are Not Enough

The equation

has infinitely many real solutions, but it has no integer solutions.

The left side is always even when \(x\) and \(y\) are integers, while the right side is odd.

Thus the integer restriction creates an arithmetic obstruction.

The GCD Solvability Test

For the linear Diophantine equation

let

Integer solutions exist exactly when

Why the GCD Must Divide \(c\)

If

has an integer solution, then \(c\) is an integer linear combination of \(a\) and \(b\).

Since

divides both \(a\) and \(b\), it divides every integer linear combination of them.

Therefore,

Why the Condition Is Sufficient

Bézout's identity guarantees integers \(u\) and \(v\) such that

where

If \(d\mid c\), write

Multiply the Bézout identity by \(k\):

Therefore an integer solution exists.

Example: No Integer Solution

Determine whether

has integer solutions.

Compute

Since

we conclude

Example: Solutions Exist

Consider

Again,

Since

integer solutions exist.

Reducing by the Greatest Common Divisor

If

divides \(c\), divide the entire equation by \(d\).

For

divide by \(6\):

The reduced coefficients \(2\) and \(3\) are relatively prime.

Finding One Particular Solution

For

inspection gives

Indeed,

Thus

is one particular solution.

From One Solution to All Solutions

Suppose

has one solution

Let

Then every integer solution is given by

Example: Complete Solution Family

Return to

We found

for the reduced equation, and

Therefore,

and

Hence

Checking the General Solution

Substitute

and

into

Then

The parameter cancels, so every integer \(t\) produces a valid solution.

Why the General Solution Has This Form

Suppose

and

both solve

Subtract the equations:

Thus

The relatively prime reduced coefficients force the differences to occur in fixed integer steps.

The Step Sizes

Let

Then moving

by

changes \(ax\) by

Moving

by

changes \(by\) by the exact opposite amount.

Therefore the total remains \(c\).

Finding One Solution with the Euclidean Algorithm

Consider

Since

solutions exist.

The Euclidean Algorithm gives

Back-Substitution

Start with

Since

substitute:

Since

we get

Since

substitute again:

A Particular Solution from Bézout's Identity

The identity

gives the particular solution

Therefore every solution to

is

Scaling a Bézout Identity

Suppose we want to solve

From

multiply by \(7\):

Therefore one solution is

All Solutions After Scaling

Since

all solutions to

are

Different particular solutions may look different but generate the same complete family.

Finding a Simpler Particular Solution

A particular solution obtained from back-substitution may be large. The parameterized family can often be used to choose a simpler representative.

For

choose \(t=2\):

Then

Thus

is another valid particular solution.

Connection to Linear Congruences

The equation

can be reduced modulo \(b\):

Solving that congruence gives possible values of \(x\), after which \(y\) can be recovered from the original equation.

Thus linear Diophantine equations and linear congruences are two views of the same divisibility structure.

Example: Solve by Congruence

Solve

Reduce modulo \(11\):

Since

we have

Because \(7\) is invertible modulo \(11\),

Completing the Congruence Method

Write

Substitute into

Simplify:

Therefore,

Positive Integer Solutions

Sometimes a problem requires

After finding the full integer family, impose these additional inequalities on the parameter.

For example, from

positivity restricts which integer values of \(t\) are allowed.

Example: Restricting the Parameter

Require

and

The first inequality gives

while the second gives

The only integer satisfying both is

Thus the only positive integer solution is

Nonnegative Integer Solutions

In counting or allocation problems, the conditions may instead be

The same method applies:

1. find the complete integer solution family;
2. translate the nonnegativity requirements into inequalities for \(t\);
3. identify the allowable integer values of \(t\).

Example: A Purchase Problem

Suppose items of one type cost \(4\) units and items of another type cost \(7\) units. We want a total cost of \(39\):

with

Reduce modulo \(4\):

Since

we obtain

so

Completing the Purchase Example

Write

Substitute:

Then

and

Thus

Nonnegativity requires

Therefore the nonnegative solutions are

Geometric View

The real solutions of

lie on a straight line in the coordinate plane.

The Diophantine solutions are the points on that line whose coordinates are both integers.

Depending on the GCD condition, the line may pass through no lattice points or through infinitely many regularly spaced lattice points.

Why Solutions Come in a Regular Pattern

Once one integer point lies on the line, every other integer solution is reached by adding the vector

an integer number of times.

Thus the integer solutions form a discrete arithmetic pattern along the line.

Common Error: Solving Over the Reals Instead of the Integers

From

ordinary algebra gives

But not every real \(x\) produces an integer \(y\).

A Diophantine equation requires both coordinates to be integers.

Common Error: Skipping the GCD Test

Before searching for solutions to

compute

If

no amount of trial and error can produce an integer solution.

Common Error: Giving Only One Solution

If one integer solution exists for a nondegenerate linear Diophantine equation in two variables, there are usually infinitely many integer solutions.

A complete answer should normally give the parameterized family

Common Error: Using the Wrong Step Sizes

The solution increments are

for \(x\), and

for \(y\).

The signs must be opposite so that the changes in \(ax\) and \(by\) cancel.

Common Error: Forgetting Domain Restrictions

A word problem may require positive or nonnegative values.

The general integer solution may include negative values that are mathematically valid but inappropriate for the application.

Always apply the problem's domain restrictions after finding the full integer family.

A Reliable Procedure for \(ax+by=c\)

1. Compute \(d=\gcd(a,b)\).
2. Check whether \(d\mid c\).
3. If \(d\nmid c\), conclude that no integer solution exists.
4. If \(d\mid c\), reduce the equation by \(d\) when convenient.
5. Find one particular integer solution by inspection, congruence, or the Extended Euclidean Algorithm.
6. Write the full family \[ x=x_0+\frac{b}{d}t,\qquad y=y_0-\frac{a}{d}t. \]
7. Let \(t\in\mathbb Z\).
8. Apply positivity, nonnegativity, or other restrictions if required.
9. Substitute to verify the solution family.

Example: Full Workflow

Solve

First,

Since

solutions exist.

Divide by \(6\):

Completing the Full Workflow

One solution to

is

because

Therefore,

and

Hence

Practice 1: Test Solvability

Determine whether

has integer solutions.

Practice 2: Find One Solution

Find one integer solution to

Practice 3: Find All Solutions

Solve completely:

Practice 4: Reduce by the GCD

Reduce

by the greatest common divisor of the coefficients.

Practice 5: Solve a Reduced Equation

Find all integer solutions to

Practice 6: Congruence Method

Solve

by first reducing modulo \(14\) or modulo \(9\).

Practice 7: Positive Integer Solutions

Find all positive integer solutions to

Practice 8: Nonnegative Solutions

Find all nonnegative integer solutions to

Practice 9: Explain the Criterion

Explain why

has no integer solutions.

Practice 10: Identify the Error

A student finds one solution

to

and says this is the complete answer.

Explain what is missing.

Practice Answers

Practice 1

Since

we conclude

Practice 2

One solution is

because

Therefore,

Practice 3

Since

and one solution is \((3,-4)\), all solutions are

Practice 4

Divide by \(12\):

Practice 5

One solution is

Therefore,

Practice 6

Reduce modulo \(14\):

The inverse of \(9\) modulo \(14\) is \(11\), because

Thus

Write

Substitute:

Then

Therefore,

Practice 7

From the earlier parameterization,

Positivity requires

only.

Therefore,

Practice 8

Divide by \(3\):

One solution is

Thus

Nonnegativity requires

Therefore,

Practice 9

But

Since every integer linear combination of \(10\) and \(15\) is divisible by \(5\), it cannot equal \(7\).

Therefore,

Practice 10

Since

one solution generates infinitely many.

From \((2,1)\),

The student gave only one particular solution rather than the complete solution family.

What to Remember

• A Diophantine equation requires integer solutions.
• For \(ax+by=c\), let \(d=\gcd(a,b)\).
• Integer solutions exist exactly when \(d\mid c\).
• Bézout's identity provides a systematic route to one particular solution.
• Once one solution \((x_0,y_0)\) is known, all solutions are \[ x=x_0+\frac{b}{d}t,\qquad y=y_0-\frac{a}{d}t. \]
• Linear congruences and linear Diophantine equations express the same divisibility structure in different forms.
• Positive or nonnegative applications require restricting the integer parameter.
• Always distinguish one particular solution from the complete family of solutions.

The central workflow is: test divisibility by the GCD, find one integer solution, then use the parameter step pattern to generate every solution.

Where We Go Next

Diophantine equations use divisibility and modular structure to control integer solutions. The next lesson, Fermat and Euler Relationships, develops powerful congruence results for powers and relatively prime integers, creating tools that later support modular inverses, large-exponent calculations, and introductory cryptography.