1. What is a Diophantine equation?
A polynomial equation $f(x_1, x_2, \ldots, x_n) = 0$ with integer coefficients, for which we ask only about integer (or sometimes rational) solutions.
Strip away the constraint and most of these equations are trivial. $3x + 5y = 7$ has infinitely many real solutions — the entire line. The interesting question is which of those line points sit exactly on the integer lattice. That tiny modification, "must be an integer," is what generates centuries of mathematics.
The name honors Diophantus of Alexandria (~3rd century CE), whose Arithmetica is the surviving text where these problems first get treated systematically. The modern field stretches from his identities all the way to Andrew Wiles's 1995 proof of Fermat's Last Theorem and beyond.
Linear Diophantine equations are completely solved by an algorithm you can run in your head. Pythagorean triples have a single clean parameterization. Pell's equation is harder but still tractable. Fermat's Last Theorem took 358 years. And Hilbert's tenth problem — "is there one algorithm that decides them all?" — is undecidable. Diophantine equations span the entire difficulty spectrum that mathematics can offer.
2. Linear Diophantine equations
The simplest non-trivial case has two unknowns and degree one:
$$ ax + by = c $$where $a, b, c$ are given integers and we look for integer $(x, y)$. The first question is whether any solution exists at all. The answer is startlingly clean.
$ax + by = c$ has integer solutions if and only if $\gcd(a, b) \mid c$.
Why? In one direction, suppose $d = \gcd(a, b)$. Then $d$ divides $a$ and $d$ divides $b$, so $d$ divides any integer combination $ax + by$. If the equation $ax + by = c$ is to hold for integers $x, y$, then $d$ must divide $c$.
In the other direction, Bézout's identity says we can always write $d = au + bv$ for some integers $u, v$ — and the extended Euclidean algorithm hands them to us. If $d \mid c$, write $c = dk$. Then
$$ a(uk) + b(vk) = (au + bv)k = dk = c, $$so $(x_0, y_0) = (uk, vk)$ is a concrete solution.
The extended Euclidean algorithm is built up in Elementary number theory. The short version: run Euclid's algorithm to compute $\gcd(a, b)$, then unwind the steps to express that gcd as $au + bv$. Every linear Diophantine problem reduces to one such run.
The full solution set
Knowing one solution $(x_0, y_0)$ gives us all of them. Suppose $(x, y)$ is any other integer solution. Subtracting:
$$ a(x - x_0) + b(y - y_0) = 0 \quad\Longrightarrow\quad a(x - x_0) = -b(y - y_0). $$Let $d = \gcd(a, b)$, and write $a = d a'$, $b = d b'$ with $\gcd(a', b') = 1$. Cancelling $d$ gives $a'(x - x_0) = -b'(y - y_0)$. Since $a'$ and $b'$ are coprime, $b'$ must divide $x - x_0$. So $x - x_0 = b' t$ for some integer $t$, and then $y - y_0 = -a' t$. Every solution has the form
$$ \boxed{\; x = x_0 + \frac{b}{d}\, t, \qquad y = y_0 - \frac{a}{d}\, t, \qquad t \in \mathbb{Z}. \;} $$One integer parameter $t$ indexes the entire infinite family. Geometrically, $(x_0, y_0)$ is one lattice point on the line $ax + by = c$, and the vector $(b/d, -a/d)$ is the smallest integer step that keeps you on the line — so the integer solutions are evenly spaced like beads on a wire.
3. Worked example: $3x + 5y = 7$
Let's solve a concrete one end-to-end, then visualize what we did.
Step 1 — Check solvability. $\gcd(3, 5) = 1$, and $1 \mid 7$. So solutions exist.
Step 2 — Find Bézout coefficients for $\gcd(3, 5)$. By inspection, $2 \cdot 3 + (-1) \cdot 5 = 1$. (You'd normally use the extended Euclidean algorithm, but for tiny numbers eyeballing it is fine.)
Step 3 — Scale up to hit $c = 7$. Multiply the Bézout equation by $7$:
$$ 14 \cdot 3 + (-7) \cdot 5 = 7. $$So $(x_0, y_0) = (14, -7)$ is one valid solution. Sanity check: $3(14) + 5(-7) = 42 - 35 = 7$. ✓
Step 4 — Write down all solutions. With $d = 1$, $b/d = 5$, and $a/d = 3$:
$$ x = 14 + 5t, \qquad y = -7 - 3t, \qquad t \in \mathbb{Z}. $$That's the complete answer. Different values of $t$ give the table below.
| $t$ | $x = 14 + 5t$ | $y = -7 - 3t$ | Check $3x + 5y$ |
|---|---|---|---|
| $-4$ | $-6$ | $5$ | $-18 + 25 = 7$ ✓ |
| $-3$ | $-1$ | $2$ | $-3 + 10 = 7$ ✓ |
| $-2$ | $4$ | $-1$ | $12 - 5 = 7$ ✓ |
| $-1$ | $9$ | $-4$ | $27 - 20 = 7$ ✓ |
| $0$ | $14$ | $-7$ | $42 - 35 = 7$ ✓ |
The "nicer" looking solution $(-1, 2)$ corresponds to $t = -3$. There's no canonical "smallest" solution — pick whichever $t$ gives you values you find readable.
Look closely at the highlighted points: each one is the previous one shifted by $(+5, -3)$. That's exactly the parameterization predicting $(b/d, -a/d) = (5, -3)$. The algebra and the picture agree.
4. Pythagorean triples
The next jump in difficulty: degree two. The Pythagorean equation
$$ x^2 + y^2 = z^2 $$asks for integer side lengths of a right triangle. Every schoolchild meets $(3, 4, 5)$ and $(5, 12, 13)$. The full classification is a small miracle: every solution comes from a clean two-parameter recipe.
A triple $(x, y, z)$ of positive integers satisfying $x^2 + y^2 = z^2$ with $\gcd(x, y, z) = 1$. Every Pythagorean triple is an integer multiple $(kx, ky, kz)$ of a primitive one, so classifying primitives classifies them all.
The primitive Pythagorean triples are exactly those of the form
$$ x = m^2 - n^2, \qquad y = 2mn, \qquad z = m^2 + n^2 $$where $m > n > 0$ are coprime integers of opposite parity (one even, one odd). Swap $x$ and $y$ to cover both orderings.
Why this gives Pythagorean triples
One direction is a one-line check:
$$ (m^2 - n^2)^2 + (2mn)^2 = m^4 - 2m^2n^2 + n^4 + 4m^2n^2 = m^4 + 2m^2n^2 + n^4 = (m^2 + n^2)^2. $$So any $(m, n)$ produces a triple. The substance lies in the converse: every primitive triple arises this way.
Why every primitive triple is captured
Start with a primitive triple $(x, y, z)$. A quick parity argument shows $z$ is odd and exactly one of $x, y$ is even — say $y$ is even, $x$ odd. Rewrite as
$$ y^2 = z^2 - x^2 = (z - x)(z + x). $$Both $z - x$ and $z + x$ are even (sum of two odds), so let $z - x = 2u$ and $z + x = 2v$. Then $y^2 = 4uv$, so $(y/2)^2 = uv$.
One checks that $\gcd(u, v) = 1$ (any common factor of $u, v$ would divide $z = u + v$ and $x = v - u$, contradicting primitivity). A product of coprime positive integers is a square only if each factor is itself a square: so $u = n^2$ and $v = m^2$ for some positive integers $n, m$. Plugging back:
$$ x = v - u = m^2 - n^2, \quad y = 2mn, \quad z = v + u = m^2 + n^2, $$and the coprimality plus parity conditions on $(m, n)$ are exactly what's needed to make $(x, y, z)$ primitive. Every primitive triple comes from such a pair.
A few triples to see the pattern
| $m$ | $n$ | $x = m^2 - n^2$ | $y = 2mn$ | $z = m^2 + n^2$ |
|---|---|---|---|---|
| $2$ | $1$ | $3$ | $4$ | $5$ |
| $3$ | $2$ | $5$ | $12$ | $13$ |
| $4$ | $1$ | $15$ | $8$ | $17$ |
| $4$ | $3$ | $7$ | $24$ | $25$ |
| $5$ | $2$ | $21$ | $20$ | $29$ |
| $6$ | $1$ | $35$ | $12$ | $37$ |
If $m$ and $n$ were both odd, every entry of $(m^2 - n^2, 2mn, m^2 + n^2)$ would be even — the triple wouldn't be primitive. If both even, $(m, n)$ wouldn't be coprime. The parity condition is what isolates the genuinely new triples from rescalings of smaller ones.
5. Pell's equation
One more degree-two equation deserves a separate treatment — and it has surprises that linear and Pythagorean problems don't.
$x^2 - D y^2 = 1$, where $D > 0$ is a fixed positive integer that is not a perfect square. We look for integer solutions $(x, y)$.
The trivial solution $(\pm 1, 0)$ exists for any $D$. The remarkable fact is that for any non-square $D$, there are infinitely many other solutions, all generated from a single one by a multiplication rule.
The structure of solutions
Define the fundamental solution $(x_1, y_1)$ to be the integer solution with $x_1 > 0$, $y_1 > 0$ that minimizes $x_1$. It always exists (this is a theorem of Lagrange; finding it uses the continued-fraction expansion of $\sqrt{D}$). Every positive solution is then obtained by raising it to integer powers in the ring $\mathbb{Z}[\sqrt{D}]$:
$$ x_n + y_n \sqrt{D} = (x_1 + y_1 \sqrt{D})^n, \qquad n = 1, 2, 3, \ldots $$Expanding the right side and matching rational and irrational parts gives integer $(x_n, y_n)$ — and the multiplicativity of $x^2 - Dy^2$ guarantees each new pair still satisfies Pell's equation.
Numeric example: $D = 2$
The equation is $x^2 - 2y^2 = 1$. The fundamental solution is $(x_1, y_1) = (3, 2)$ — verify: $9 - 8 = 1$. ✓
To get the next solution, expand $(3 + 2\sqrt{2})^2$:
$$ (3 + 2\sqrt{2})^2 = 9 + 12\sqrt{2} + 8 = 17 + 12\sqrt{2}, $$so $(x_2, y_2) = (17, 12)$, and indeed $17^2 - 2 \cdot 12^2 = 289 - 288 = 1$. Cubing $(3 + 2\sqrt{2})$ gives $(99, 70)$, and $99^2 - 2 \cdot 70^2 = 9801 - 9800 = 1$. The solutions grow exponentially in size.
| $n$ | $x_n$ | $y_n$ | $x_n^2 - 2 y_n^2$ |
|---|---|---|---|
| $1$ | $3$ | $2$ | $9 - 8 = 1$ ✓ |
| $2$ | $17$ | $12$ | $289 - 288 = 1$ ✓ |
| $3$ | $99$ | $70$ | $9801 - 9800 = 1$ ✓ |
| $4$ | $577$ | $408$ | $332929 - 332928 = 1$ ✓ |
The ratios $x_n / y_n$ in that table are $1.5, 1.4166\ldots, 1.4142857\ldots, 1.41421568\ldots$ — convergents to $\sqrt{2} = 1.41421356\ldots$ This is no coincidence: Pell's equation is intimately tied to the continued-fraction expansion of $\sqrt{D}$, and its solutions are exactly the best rational approximations.
If $D$ is a perfect square, say $D = k^2$, then $x^2 - D y^2 = (x - ky)(x + ky) = 1$ forces $x \pm ky \in \{\pm 1\}$, leaving only the trivial solutions. The non-square condition is what makes the equation interesting.
6. Fermat's Last Theorem
Move from degree two to degree three, and the landscape changes entirely.
For any integer $n \geq 3$, the equation $x^n + y^n = z^n$ has no solution in positive integers $x, y, z$.
Pierre de Fermat wrote in the margin of his copy of Diophantus's Arithmetica around 1637 that he had "a truly marvellous proof" of this statement, but that the margin was "too narrow to contain it." Whatever Fermat actually had, no one ever found it — and the conjecture stood unsolved for $358$ years.
Special cases fell over the centuries: Fermat himself proved $n = 4$ by his method of infinite descent; Euler proved $n = 3$ (with a small gap, later filled); Sophie Germain made deep progress in the early 19th century; Kummer's work on $n$ prime led to the entire theory of ideal numbers and modern algebraic number theory.
The full result was finally proved by Andrew Wiles in 1995 (with a key gap closed in collaboration with Richard Taylor). The proof does not look anything like number theory at the level we have been doing here. It works by establishing a special case of the Taniyama–Shimura–Weil conjecture, which relates elliptic curves to modular forms — a deep connection in arithmetic geometry. A counterexample $(x, y, z, n)$ to Fermat would produce an elliptic curve (the Frey curve) with properties forbidden by the modularity theorem; therefore no counterexample can exist.
The techniques used by Wiles were developed over the 20th century and have no plausible elementary substitute. Most mathematicians believe Fermat had at most a flawed argument that he later realized didn't generalize beyond small cases. The statement is elementary; the proof, decisively, is not.
7. Hilbert's tenth problem
If linear Diophantine equations are solved by an algorithm, and Pythagorean and Pell equations have clean structure, a natural question follows: is there one master algorithm that decides solvability of any Diophantine equation?
In 1900, David Hilbert posed this as the tenth problem in his famous list of $23$ unsolved problems for the new century. He asked, essentially: Find a procedure that, given any polynomial equation with integer coefficients in any number of variables, decides in finitely many steps whether it has an integer solution.
The answer, established in 1970 by Yuri Matiyasevich building on decades of work by Martin Davis, Hilary Putnam, and Julia Robinson, is striking: no such algorithm exists. The set of Diophantine equations that have integer solutions is precisely the set of recursively enumerable (Turing-recognizable) sets — meaning Diophantine equations can encode arbitrary computation, including the halting problem. Deciding whether $f(x_1, \ldots, x_n) = 0$ has an integer solution is at least as hard as deciding whether a Turing machine halts, which is provably undecidable.
This is not "we haven't found an algorithm yet." It's a theorem that no algorithm can exist, no matter how clever. The world of Diophantine equations is, viewed as a whole, beyond the reach of any uniform procedure — even though specific families (linear, Pythagorean, Pell) are completely solved. Individual problems can be hard; the general problem is impossible.
8. Common pitfalls
Before solving $ax + by = c$, verify $\gcd(a, b) \mid c$. If it doesn't, the equation has zero integer solutions — and any algebraic manipulation you do afterwards will produce nonsense.
Euclid's $(m, n)$ parameterization generates only primitive Pythagorean triples. The triples $(6, 8, 10)$, $(9, 12, 15)$, $(30, 40, 50)$ are all valid Pythagorean triples, but they are integer multiples of $(3, 4, 5)$, not new outputs of the recipe.
$x^2 - 4 y^2 = 1$ has only $(\pm 1, 0)$, not infinitely many solutions. The non-square hypothesis on $D$ is essential — without it the left side factors over the integers and collapses the problem.
For some families of Diophantine equations (e.g., elliptic curves), we know the set of solutions is finite — but the proofs are ineffective, meaning they give no upper bound on how large solutions can be. You can't always turn a finiteness theorem into a search algorithm.
9. Worked examples
Each example reinforces a different recipe. Try them yourself before opening the solution.
Example 1 · Solve $6x + 9y = 15$ in integers.
Step 1. $\gcd(6, 9) = 3$, and $3 \mid 15$. Solvable.
Step 2. Divide through by $3$ to simplify: $2x + 3y = 5$.
Step 3. Bézout for $\gcd(2, 3) = 1$: $(-1)(2) + (1)(3) = 1$. Scale by $5$: $(-5)(2) + (5)(3) = 5$.
So $(x_0, y_0) = (-5, 5)$ is one solution. (You can also spot $(1, 1)$ by inspection.)
Step 4. General solution: $x = -5 + 3t$, $y = 5 - 2t$, $t \in \mathbb{Z}$. Equivalently, using $(1, 1)$ as the base, $x = 1 + 3t$, $y = 1 - 2t$.
Example 2 · Show $6x + 9y = 7$ has no integer solutions.
$\gcd(6, 9) = 3$. Does $3 \mid 7$? No. Therefore no integer solutions exist. (Equivalently: the left side is always a multiple of $3$, but $7$ is not.)
Example 3 · Find the primitive Pythagorean triple from $(m, n) = (5, 2)$.
Check the conditions: $\gcd(5, 2) = 1$ ✓, opposite parity (odd, even) ✓.
$x = 25 - 4 = 21$, $\quad y = 2 \cdot 5 \cdot 2 = 20$, $\quad z = 25 + 4 = 29$.
Verify: $21^2 + 20^2 = 441 + 400 = 841 = 29^2$. ✓
Example 4 · Find the next solution after $(3, 2)$ for $x^2 - 2y^2 = 1$.
Compute $(3 + 2\sqrt{2})^2 = 9 + 12\sqrt{2} + 8 = 17 + 12\sqrt{2}$.
So $(x_2, y_2) = (17, 12)$. Check: $17^2 - 2 \cdot 12^2 = 289 - 288 = 1$. ✓
Example 5 · Is $(15, 8, 17)$ a primitive Pythagorean triple? If so, find $(m, n)$.
$\gcd(15, 8, 17) = 1$, and $15^2 + 8^2 = 225 + 64 = 289 = 17^2$. Primitive. ✓
Match against the recipe. Since the even leg is $8 = 2mn$, we have $mn = 4$. The odd leg $15 = m^2 - n^2$ then forces $(m, n) = (4, 1)$ (check: $16 - 1 = 15$ ✓).
Confirm: $z = 16 + 1 = 17$. ✓