Examples of Solving Diophantine Equations: Practical, Step‑by‑Step Examples

Let’s skip the formalities and go straight to work. A Diophantine equation is just an equation where we only care about integer solutions. No decimals, no fractions, just whole numbers (sometimes including negatives).

A classic starting point is a linear Diophantine equation in two variables:

\[ ax + by = c, \quad x, y \in \mathbb{Z}. \]

Here’s a very friendly example of solving a Diophantine equation: practical example number one:

Example 1 – Buying tickets with exact change
Suppose concert tickets cost \(7 for students and \)11 for adults. You spend exactly $100. How many of each ticket could you have bought?

We want integer solutions to
\[ 7s + 11a = 100, \]
where \(s\) is the number of student tickets and \(a\) is the number of adult tickets.

Step 1: Check if any solution is possible

Look at the greatest common divisor (gcd) of 7 and 11. Since 7 and 11 are both prime and different, \(\gcd(7,11) = 1\). Because 1 divides 100, there might be solutions.

If the gcd did not divide 100, there would be no integer solution at all. This simple gcd test is one of the best examples of a quick filter in number theory.

Step 2: Find one solution

Try to solve \(7s + 11a = 100\) by trial and error:

If \(a = 1\): \(7s + 11 = 100 \Rightarrow 7s = 89\) (not divisible by 7).

If \(a = 2\): \(7s + 22 = 100 \Rightarrow 7s = 78\) (not divisible by 7).

If \(a = 3\): \(7s + 33 = 100 \Rightarrow 7s = 67\) (no).

If \(a = 4\): \(7s + 44 = 100 \Rightarrow 7s = 56 \Rightarrow s = 8.\)

So \((s,a) = (8,4)\) is one integer solution.

Step 3: Describe all solutions

For linear Diophantine equations, once you have one solution, you can generate infinitely many (including negative ones) using a parameter.

General theory says: if \((s_0,a_0)\) is one solution of \(7s+11a=100\), then all integer solutions are
[
s = s_0 + 11t, \quad a = a_0 - 7t, \quad t \in \mathbb{Z}.
]

Here, \((s_0,a_0) = (8,4)\), so
[
s = 8 + 11t, \quad a = 4 - 7t.
]

To keep \(s,a\) nonnegative (because you can’t buy negative tickets), we need:

• \(8 + 11t \ge 0\)
• \(4 - 7t \ge 0\)

From \(4 - 7t \ge 0\) we get \(t \le 4/7\), so \(t \le 0\) as an integer. From \(8 + 11t \ge 0\), we get \(t \ge -8/11\), so \(t \ge -1\).

So \(t\) can be \(-1\) or \(0\):

• If \(t = 0\): \((s,a) = (8,4)\).
• If \(t = -1\): \((s,a) = (8 - 11, 4 + 7) = (-3,11)\), but \(s = -3\) is not allowed.

So the only nonnegative solution is \((s,a) = (8,4)\): 8 student tickets and 4 adult tickets.

That’s our first concrete example of solving a Diophantine equation: practical example with a real‑world flavor.

More linear examples include time, distance, and scheduling

To build confidence, let’s look at more examples of solving Diophantine equations: practical examples that appear in everyday puzzles.

Example 2 – Meeting times for buses

Two buses leave a station at the same time. One returns every 18 minutes, the other every 24 minutes. After how many minutes will they both be back at the station together?

This is really an LCM (least common multiple) problem, but you can frame it as a Diophantine equation. We want integers \(m,n\) such that
[
18m = 24n.
]

Divide both sides by 6:
[
3m = 4n.
]

We want integer solutions. Treat this as a Diophantine equation:
[
3m - 4n = 0.
]

One solution is \((m,n) = (4,3)\). All solutions are \(m = 4k, n = 3k\). The smallest positive time is when \(k=1\):
[
18m = 18 \cdot 4 = 72 \text{ minutes}.
]

So they meet again after 72 minutes. This is a simple example of how Diophantine thinking connects to LCMs and scheduling.

Example 3 – Integer solutions to a linear constraint

Find all integer pairs \((x,y)\) such that
[
5x - 13y = 1.
]

First, note \(\gcd(5,13) = 1\), so solutions exist. Use the extended Euclidean algorithm (a standard method taught in number theory courses; you can find a formal description in many lecture notes, such as those hosted by MIT OpenCourseWare at ocw.mit.edu).

We want integers \(x,y\) with \(5x - 13y = 1\). Rearrange as
[
5x + 13(-y) = 1.
]

Compute:

• \(13 = 2\cdot5 + 3\)
• \(5 = 1\cdot3 + 2\)
• \(3 = 1\cdot2 + 1\)
• \(2 = 2\cdot1 + 0\)

Back‑substitute:

• \(1 = 3 - 1\cdot2\)
• \(2 = 5 - 1\cdot3\)
• So \(1 = 3 - (5 - 3) = 2\cdot3 - 5\)
• And \(3 = 13 - 2\cdot5\)
• Thus \(1 = 2(13 - 2\cdot5) - 5 = 2\cdot13 - 5\cdot5\)

So \(1 = 2\cdot13 + (-5)\cdot5\), which means one solution to \(5x - 13y = 1\) is
[
x = -5, \quad -y = 2 \Rightarrow y = -2.
]

All integer solutions are
[
x = -5 + 13t, \quad y = -2 + 5t, \quad t \in \mathbb{Z}.
]

This is another clean example of solving a Diophantine equation: practical example that also teaches you how the extended Euclidean algorithm produces solutions.

Moving beyond linear: quadratic examples of solving Diophantine equations

Linear equations are the warm‑up. Some of the best examples of Diophantine equations in number theory are quadratic, especially equations like
[
x^2 - Dy^2 = 1,
]
known as Pell’s equation.

These show up in surprising places, including continued fractions and approximations to square roots. While this might sound abstract, we can still treat them as practical examples if we walk through the steps.

Example 4 – A small Pell‑type equation

Solve in integers:
[
x^2 - 2y^2 = 1.
]

Try small values of \(y\):

• If \(y = 0\): \(x^2 = 1 \Rightarrow x = \pm 1\). So \((x,y) = (1,0),(-1,0)\) are solutions.
• If \(y = 1\): \(x^2 - 2 = 1 \Rightarrow x^2 = 3\) (no integer solution).
• If \(y = 2\): \(x^2 - 8 = 1 \Rightarrow x^2 = 9 \Rightarrow x = \pm 3\). So \((3,2)\) and \((-3,2)\) are solutions.

One of the famous facts (proved in many textbooks and lecture notes, such as those from Harvard’s math department) is that from a fundamental solution like \((3,2)\), you can generate infinitely many others using algebraic methods.

Even if you don’t go that far, seeing a concrete example of Pell’s equation gives you a feel for how quadratic Diophantine equations behave very differently from linear ones: there are still infinitely many solutions, but they’re much more structured.

Example 5 – Pythagorean triples

Another classic family of quadratic Diophantine equations is
[
x^2 + y^2 = z^2.
]

Solutions in positive integers \((x,y,z)\) are called Pythagorean triples. Some of the best examples include:

• \((3,4,5)\)
• \((5,12,13)\)
• \((8,15,17)\)

These show up in geometry, physics, and even in coding interviews when someone wants a “nice” right triangle with integer sides.

There’s a well‑known formula: every primitive Pythagorean triple (where \(x,y,z\) share no common factor) can be written as
[
x = m^2 - n^2, \quad y = 2mn, \quad z = m^2 + n^2,
]
for integers \(m > n > 0\). For example, take \(m=2, n=1\):

• \(x = 2^2 - 1^2 = 3\)
• \(y = 2\cdot2\cdot1 = 4\)
• \(z = 2^2 + 1^2 = 5\)

So \((3,4,5)\) is a Pythagorean triple.

This is a powerful example of solving Diophantine equations: practical examples that connect algebra to geometry.

Real examples: coin problems and integer constraints

Diophantine equations also appear whenever you’re forced to use discrete units: coins, tickets, boxes, people, and so on. Here are more real examples of solving Diophantine equations: practical examples you might see in contests or puzzle books.

Example 6 – Coin change in whole dollars

Suppose a vending machine only takes \(0.25 and \)0.40 coins (imagine some odd foreign coin system). You want to pay exactly $4.45. How many of each coin can you use?

Let \(q\) be the number of 25‑cent coins and \(c\) the number of 40‑cent coins. Then
[
25q + 40c = 445.
]

First, divide everything by 5:
[
5q + 8c = 89.
]

Now solve this linear Diophantine equation.

Check gcd: \(\gcd(5,8) = 1\), which divides 89, so integer solutions exist.

We want one particular solution. Try small values of \(c\):

• If \(c = 1\): \(5q + 8 = 89 \Rightarrow 5q = 81\) (no).
• If \(c = 2\): \(5q + 16 = 89 \Rightarrow 5q = 73\) (no).
• If \(c = 3\): \(5q + 24 = 89 \Rightarrow 5q = 65 \Rightarrow q = 13.\)

So \((q,c) = (13,3)\) is one solution.

General solutions are
[
q = 13 + 8t, \quad c = 3 - 5t, \quad t \in \mathbb{Z}.
]

To keep \(q,c \ge 0\):

• \(3 - 5t \ge 0 \Rightarrow t \le 3/5 \Rightarrow t \le 0\).
• \(13 + 8t \ge 0 \Rightarrow t \ge -13/8 \Rightarrow t \ge -1\).

So \(t = -1\) or \(0\):

• If \(t = 0\): \((q,c) = (13,3)\).
• If \(t = -1\): \((q,c) = (5,8)\).

So there are two ways to pay exactly $4.45: 13 quarters and 3 forty‑cent coins, or 5 quarters and 8 forty‑cent coins.

This is another clear example of solving a Diophantine equation: practical example that feels like a real‑life money puzzle.

Example 7 – Boxes and items

A warehouse stores items in boxes that hold either 9 or 14 items. An order comes in for exactly 191 items. Is it possible to fulfill the order using only full boxes?

Let \(x\) be the number of 9‑item boxes and \(y\) the number of 14‑item boxes:
[
9x + 14y = 191.
]

Check gcd: \(\gcd(9,14) = 1\), which divides 191, so integer solutions exist.

Find one solution. Work modulo 9:
[
9x + 14y \equiv 14y \equiv 191 \pmod{9}.
]

Compute:

• \(14 \equiv 5 \pmod{9}\)
• \(191 \equiv 191 - 9\cdot21 = 191 - 189 = 2 \pmod{9}\)

So \(5y \equiv 2 \pmod{9}\). The inverse of 5 mod 9 is 2 (since \(5\cdot2 = 10 \equiv 1 \pmod{9}\)). Multiply both sides by 2:
[
y \equiv 4 \pmod{9}.
]

So \(y = 4 + 9k\). Plug into the original equation:
[
9x + 14(4 + 9k) = 191 \Rightarrow 9x + 56 + 126k = 191.
]

So
[
9x = 135 - 126k = 9(15 - 14k) \Rightarrow x = 15 - 14k.
]

We need \(x,y \ge 0\):

• \(y = 4 + 9k \ge 0\) gives \(k \ge -4/9 \Rightarrow k \ge 0\).
• \(x = 15 - 14k \ge 0\) gives \(k \le 15/14 \Rightarrow k \le 1\).

So \(k = 0\) or \(1\):

• If \(k = 0\): \((x,y) = (15,4)\).
• If \(k = 1\): \((x,y) = (1,13)\).

So it is possible, and there are two different packing strategies.

Again, this is a solid example of solving a Diophantine equation: practical example in logistics or operations.

Modern contexts: coding, cryptography, and algorithmic examples

Diophantine equations aren’t just old‑fashioned number puzzles. They show up in modern algorithms, especially when we care about modular arithmetic and integer constraints.

Example 8 – Modular inverse in cryptography

In many cryptographic algorithms (for example, RSA, described in detail by NIST at nist.gov), you need to find a modular inverse. That’s a Diophantine problem.

Suppose you need to find the inverse of 17 modulo 312. You want an integer \(x\) such that
[
17x \equiv 1 \pmod{312}.
]

This is equivalent to the Diophantine equation
[
17x - 312k = 1
]
for some integers \(x,k\).

Use the extended Euclidean algorithm to solve \(17x - 312k = 1\). Compute gcd(17,312):

• \(312 = 17\cdot18 + 6\)
• \(17 = 6\cdot2 + 5\)
• \(6 = 5\cdot1 + 1\)
• \(5 = 1\cdot5 + 0\)

Back‑substitute:

• \(1 = 6 - 5\)
• \(5 = 17 - 6\cdot2\)
• So \(1 = 6 - (17 - 6\cdot2) = 3\cdot6 - 17\)
• And \(6 = 312 - 17\cdot18\)
• Thus \(1 = 3(312 - 17\cdot18) - 17 = 3\cdot312 - 55\cdot17\)

So
[

-55\cdot17 + 3\cdot312 = 1.
]

That means \(x = -55\) is a solution. Modulo 312, \(-55 \equiv 312 - 55 = 257\). So the modular inverse of 17 mod 312 is 257.

This is a very modern example of solving a Diophantine equation: practical example that underpins secure communication.

Example 9 – Constraint solving in code

In competitive programming and algorithm design, you often see constraints like:
[
3x + 7y \le 100, \quad x,y \in \mathbb{Z}_{\ge0}.
]

To check feasibility or count solutions, programmers often start by solving the boundary equation
[
3x + 7y = 100,
]
which is a Diophantine equation.

Check gcd: \(\gcd(3,7) = 1\), so integer solutions exist. Solve for one solution by trying values of \(y\):

• If \(y = 1\): \(3x + 7 = 100 \Rightarrow 3x = 93 \Rightarrow x = 31\).

So \((x,y) = (31,1)\) is one solution. General solutions are
[
x = 31 + 7t, \quad y = 1 - 3t.
]

To keep \(x,y \ge 0\), you’d bound \(t\) just like in earlier examples. This pattern appears constantly in coding problems where you have to satisfy integer constraints.

FAQ: Common questions about examples of solving Diophantine equations

Q1. Can you give another simple example of a Diophantine equation with no solution?
Yes. Consider
[
6x + 9y = 20.
]
The left side is always a multiple of 3, because \(6x\) and \(9y\) are each multiples of 3. But 20 is not a multiple of 3. So there is no integer solution. This is a quick example of solving a Diophantine equation by using the gcd test and immediately spotting impossibility.

Q2. What’s an example of a Diophantine equation used in real research or applications?
One important family is Pell’s equations \(x^2 - Dy^2 = 1\), which appear in algorithms for approximating square roots and in algebraic number theory. These are studied in university‑level courses and research; you can find more discussion in open course materials from places like MIT OpenCourseWare and Harvard’s math resources.

Q3. Are there Diophantine equations that are impossible to solve in general?
Yes, in a certain sense. Hilbert’s Tenth Problem asked for a general algorithm to decide whether any given Diophantine equation has an integer solution. In 1970, Yuri Matiyasevich, building on work by Davis, Putnam, and Robinson, showed that no such algorithm exists. The American Mathematical Society has accessible historical notes at ams.org explaining this result. So while we have many methods and lots of practical examples of solving Diophantine equations, there is no single algorithm that works for every possible Diophantine equation.

Q4. How can I practice more examples of solving Diophantine equations: practical examples, not just theory?
Good sources include problem sets from university number theory courses (often public on .edu sites), math contest archives like the AMC/AIME problems, and online judge platforms for programming. Look specifically for problems involving “integer solutions,” “coin problems,” “Pythagorean triples,” and “modular inverses.” These all hide Diophantine equations under the surface.

Q5. Is there a quick checklist for tackling a new Diophantine equation?
A simple mental checklist many students find helpful is:

• First, check the gcd condition if the equation is linear.
• Second, look for obvious factorizations or patterns (for quadratics, think about Pythagorean or Pell‑type forms).
• Third, try to find one solution, then express all solutions using a parameter.
• Finally, apply any extra real‑world constraints (nonnegativity, upper bounds, etc.) to narrow down to acceptable answers.

Working through the best examples of solving Diophantine equations—practical examples like the ones above—will train you to apply this checklist almost automatically.