Diophantine Equations

A Diophantine equation is a polynomial equation for which we only accept whole-number solutions. That single restriction — insisting on integers rather than any real number — transforms familiar algebra into some of the deepest and most stubborn problems in mathematics. The equation $2x + 3y = 12$ has infinitely many real solutions (it is just a line), but asking which of its points have integer coordinates is a genuinely different question with its own beautiful structure.

Why should a constraint make things harder? Because the integers are "sparse." When you can use any real number, you can always slide continuously toward a solution. Integers give you no room to slide — you either land exactly on a lattice point or you miss. This is why an innocent-looking equation like $x^n + y^n = z^n$ could resist the world's best mathematicians for over 350 years. Let's learn the tools that tame the solvable cases and understand why the hard cases are so hard.

Learning Objectives

• Define a Diophantine equation and explain why demanding integer solutions changes the problem.
• Determine when a linear Diophantine equation $ax + by = c$ has solutions, using the greatest common divisor.
• Find all integer solutions using the extended Euclidean algorithm and write the general solution.
• Recognize and generate Pythagorean triples as a classic nonlinear Diophantine problem.
• Tell the historical story of Fermat's Last Theorem and understand, at a high level, what Andrew Wiles proved.
• Avoid the most common errors students make with divisibility and general solutions.

Quick Answer

A Diophantine equation asks for integer (whole-number) solutions to a polynomial equation. The linear case $ax + by = c$ is completely solved: solutions exist if and only if $\gcd(a,b)$ divides $c$. When they exist, there are infinitely many, and the extended Euclidean algorithm produces one particular solution from which all others follow. Nonlinear cases are far richer: $x^2 + y^2 = z^2$ has infinitely many solutions (Pythagorean triples), while $x^n + y^n = z^n$ has no positive-integer solutions for any $n \ge 3$ — this is Fermat's Last Theorem, conjectured around 1637 and finally proved by Andrew Wiles in 1994.

Where It Came From

The subject is named for Diophantus of Alexandria, a Greek mathematician of roughly the 3rd century CE, whose thirteen-book treatise Arithmetica collected problems calling for rational and whole-number answers. Diophantus did not study these equations for abstract sport; his problems grew out of practical arithmetic — dividing quantities, splitting sums, and finding numbers meeting several conditions at once. Real commerce and inheritance forced a recurring question: "I need a whole number of coins, not a fraction — which whole numbers actually work?" That is the motivating need behind the entire field. You cannot pay someone $2.5$ chickens; indivisible goods make integer constraints unavoidable.

The genius of Arithmetica was its shift toward symbolic manipulation and its focus on solutions in the "counting numbers." For over a thousand years it was a touchstone for anyone thinking about number puzzles. Its most famous moment came in 1637, when the French lawyer and amateur mathematician Pierre de Fermat, reading a Latin edition beside Problem II.8 (splitting a square into two squares), scribbled in the margin his claim that the analogous equation with cubes, fourth powers, and beyond had no solutions — adding that he had a "truly marvelous proof" the margin was too small to contain. That note launched three and a half centuries of effort.

The systematic theory of the linear case matured through the work of mathematicians like Bachet (who edited the very edition Fermat annotated) and reached full generality with the tools of Euclid's algorithm, formalized in modern terms by Euler, Lagrange, and Gauss. So the field spans two very different achievements: a complete, algorithmic theory for linear equations, and a landscape of individually hard nonlinear problems that continues to drive research today.

Linear Diophantine Equations: When Do Solutions Exist?

Consider $ax + by = c$ where $a$, $b$, $c$ are given integers and we seek integer $x$, $y$. The complete criterion is elegant:

Existence Theorem. $ax + by = c$ has an integer solution if and only if $\gcd(a,b)$ divides $c$.

The reason is simple once you see it. Any combination $ax + by$ is automatically a multiple of $d = \gcd(a,b)$, because $d$ divides both $a$ and $b$. So the left side can only ever equal multiples of $d$. If $c$ is not such a multiple, no integers can work. Conversely, Bézout's identity guarantees that $d$ itself is expressible as $ax + by$, and scaling that expression reaches any multiple of $d$.

Worked example (no solution). Does $6x + 9y = 20$ have integer solutions? Here $\gcd(6,9) = 3$. Does $3$ divide $20$? No, since $20 = 3 \times 6 + 2$. Therefore no integer solutions exist — every value of $6x + 9y$ is a multiple of $3$, and $20$ is not.

Worked example (solutions exist). Does $6x + 9y = 21$ have solutions? Now $\gcd(6,9) = 3$ and $3$ divides $21$ (since $21 = 3 \times 7$). Yes — solutions exist, and we will find them next.

Finding All Solutions: The Extended Euclidean Algorithm

Existence is only half the story. To find solutions we use the extended Euclidean algorithm, which not only computes $\gcd(a,b)$ but also expresses it as $ax_0 + by_0$.

Worked example. Solve $6x + 9y = 21$ completely.

Step 1 — the gcd via Euclid. Divide the larger by the smaller repeatedly: $9 = 1 \times 6 + 3$ $6 = 2 \times 3 + 0$ The last nonzero remainder is $3$, so $\gcd(6,9) = 3$. Good — it divides $21$.

Step 2 — back-substitute to write the gcd as a combination. From the first line, $3 = 9 - 1 \times 6.$ So $6(-1) + 9(1) = 3$. A particular solution to $6x + 9y = 3$ is $x = -1$, $y = 1$.

Step 3 — scale to the target. We want the right side to be $21 = 3 \times 7$, so multiply through by $7$: $6(-7) + 9(7) = 21.$ A particular solution is $x_0 = -7$, $y_0 = 7$. Check: $6(-7) + 9(7) = -42 + 63 = 21$. Correct.

Step 4 — the general solution. Once you have one solution, all others come from adding to $x$ and subtracting from $y$ in steps that keep the equation balanced. The general solution of $ax + by = c$ is $x = x_0 + \frac{b}{d}\,t, \qquad y = y_0 - \frac{a}{d}\,t, \qquad t \in \mathbb{Z},$ where $d = \gcd(a,b)$. Here $d = 3$, $b/d = 3$, $a/d = 2$, so $x = -7 + 3t, \qquad y = 7 - 2t.$

Let us verify one more value. Take $t = 3$: $x = -7 + 9 = 2$, $y = 7 - 6 = 1$. Check: $6(2) + 9(1) = 12 + 9 = 21$. Correct. Notice how the $b/d$ and $a/d$ steps guarantee the changes cancel: $6(+3t) + 9(-2t) = 18t - 18t = 0$.

A real coin problem. Suppose you must pay exactly $43$ cents using only $5$-cent and $9$-cent tokens: solve $5x + 9y = 43$ with $x, y \ge 0$. Since $\gcd(5,9)=1$ divides $43$, solutions exist. Euclid gives $9 = 1\times 5 + 4$, $5 = 1\times 4 + 1$, so $1 = 5 - 1\times 4 = 5 - (9 - 5) = 2\times 5 - 1\times 9$. Scaling by $43$: $x_0 = 86$, $y_0 = -43$. General solution $x = 86 + 9t$, $y = -43 - 5t$. To make both nonnegative we need $y \ge 0 \Rightarrow t \le -8.6$ and $x \ge 0 \Rightarrow t \ge -9.55$, so $t = -9$: $x = 86 - 81 = 5$, $y = -43 + 45 = 2$. Check: $5(5) + 9(2) = 25 + 18 = 43$. So five $5$-cent tokens and two $9$-cent tokens work.

Nonlinear Case: Pythagorean Triples

The most famous nonlinear Diophantine equation is $x^2 + y^2 = z^2$, whose positive-integer solutions are the Pythagorean triples — the side lengths of right triangles with whole-number sides, like $(3,4,5)$ and $(5,12,13)$.

Unlike a single quadratic in one variable, this equation has infinitely many solutions, and they can all be generated. Choose integers $m > n > 0$ and set $a = m^2 - n^2, \qquad b = 2mn, \qquad c = m^2 + n^2.$ Then $a^2 + b^2 = c^2$ automatically.

Worked example. Take $m = 3$, $n = 2$: $a = 9 - 4 = 5, \qquad b = 2 \times 3 \times 2 = 12, \qquad c = 9 + 4 = 13.$ Check: $5^2 + 12^2 = 25 + 144 = 169 = 13^2$. This is exactly the $(5,12,13)$ triple. The algebra works because $(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$.

This constructive richness is precisely what makes Fermat's claim so startling: swap the exponent $2$ for $3$ and every solution vanishes.

Fermat's Last Theorem: The 358-Year Problem

Fermat's marginal note asserts:

For any integer $n \ge 3$, the equation $x^n + y^n = z^n$ has no solutions in positive integers $x$, $y$, $z$.

For $n = 2$ we have infinitely many solutions. For $n \ge 3$, none. Fermat almost certainly did not possess a general proof; he later proved only the case $n = 4$, using his method of infinite descent (showing any solution would force a smaller one, an impossible regress). Over the next centuries, Euler settled $n = 3$, Sophie Germain made sweeping progress on a whole class of exponents, and Dirichlet and Legendre handled $n = 5$. But each case fell only to enormous, exponent-specific effort — no unified argument appeared.

The breakthrough came from an unexpected direction. In the 1980s it was recognized (via work connecting to the Taniyama–Shimura conjecture, which links elliptic curves to modular forms) that a hypothetical Fermat solution would produce an elliptic curve too strange to be "modular." If every such curve must be modular, no Fermat solution can exist. Andrew Wiles, after seven years of largely secret work at Princeton, announced a proof in 1993. A gap surfaced during review, but Wiles — with help from his former student Richard Taylor — repaired it, and the complete proof was published in 1994 (appearing in Annals of Mathematics in 1995). The proof runs to over a hundred pages of deep modern machinery — nothing that could ever have fit in a margin.

The lesson is profound: a question a schoolchild can state required inventing and connecting entire branches of twentieth-century mathematics to answer.

Real-World Applications

• Cryptography. RSA and related systems rest on modular arithmetic and the extended Euclidean algorithm — the same tool that solves linear Diophantine equations is used to compute the private decryption key from the public one.
• Making change and resource allocation. Any "exact amount from fixed denominations" problem (vending machines, cash registers, postage from stamps of fixed values) is a linear Diophantine problem with nonnegativity constraints — the classic Frobenius coin problem.
• Scheduling and calendars. The Chinese Remainder Theorem, a Diophantine cousin, solves "an event recurs every $4$ days and another every $6$ days — when do they coincide?" and underlies clock arithmetic and error-correcting codes.
• Integer programming. Optimizing over whole-number quantities (you cannot ship half a container) is Diophantine constraint-solving at industrial scale.

Common Mistakes

Mistake 1: Assuming a solution always exists. Students often try to "solve" $6x + 9y = 20$ and get frustrated. Why it is wrong: the left side is always a multiple of $\gcd(6,9)=3$, and $20$ is not. Correction: Always test the divisibility condition first — solutions exist iff $\gcd(a,b) \mid c$.

Mistake 2: Finding one solution and stopping. A Diophantine equation with a solution has infinitely many. Why it is wrong: reporting only $x_0, y_0$ hides the full answer and misses solutions in a required range (like nonnegative ones). Correction: Always write the general solution $x = x_0 + (b/d)t$, $y = y_0 - (a/d)t$.

Mistake 3: Using $a$ and $b$ instead of $a/d$ and $b/d$ in the step size. Writing $x = x_0 + bt$, $y = y_0 - at$ does keep the equation balanced but skips solutions when $d > 1$. Why it is wrong: the smallest valid step is $b/d$, not $b$. Correction: divide both coefficients by the gcd in the general formula.

Mistake 4 (bonus): Believing Fermat's Last Theorem fails for $n = 2$. It does not "fail" — $n = 2$ is simply outside the theorem's claim, which is only about $n \ge 3$. The existence of Pythagorean triples is fully consistent with FLT.

Comparison and Connections

Feature	Linear Diophantine $ax+by=c$	Pythagorean $x^2+y^2=z^2$	Fermat $x^n+y^n=z^n,\ n\ge3$
Solutions exist?	Iff $\gcd(a,b)\mid c$	Yes, infinitely many	No positive solutions
Method	Extended Euclidean algorithm	Parametric formula $(m,n)$	Proof of non-existence (Wiles)
Difficulty	Fully solved, algorithmic	Fully classified	Required centuries
Number of solutions	$0$ or $\infty$	$\infty$	$0$

Diophantine analysis sits at the heart of number theory, drawing on the Euclidean algorithm and modular arithmetic and feeding into algebraic geometry (elliptic curves) and cryptography. Do not confuse a Diophantine equation with an ordinary algebraic one: the equation may be identical; it is the insistence on integer solutions that defines the discipline.

Practice Questions

Recall

State the precise condition under which $ax + by = c$ has an integer solution.

Answer: It has a solution if and only if $\gcd(a,b)$ divides $c$.

Understanding

Explain in your own words why $4x + 6y = 9$ has no integer solutions.

Guidance: $\gcd(4,6) = 2$. The left side is always even (a multiple of $2$), but $9$ is odd, so equality is impossible.

Application

Find the general integer solution of $3x + 5y = 1$.

Answer: $\gcd(3,5)=1 \mid 1$. Euclid: $5 = 1\times3 + 2$, $3 = 1\times2 + 1$, so $1 = 3 - 1\times2 = 3 - (5-3) = 2\times3 - 1\times5$. Thus $x_0 = 2$, $y_0 = -1$. General solution: $x = 2 + 5t$, $y = -1 - 3t$. Check ($t=0$): $3(2)+5(-1)=6-5=1$. Correct.

Analysis

The equation $x^3 + y^3 = z^3$ has no positive-integer solutions, yet $3^3 + 4^3 + 5^3 = 6^3$ is true. Does the second fact contradict Fermat's Last Theorem? Explain.

Guidance: No contradiction. FLT concerns a sum of two cubes equaling a cube ($x^3 + y^3 = z^3$). The identity $27 + 64 + 125 = 216$ is a sum of three cubes equaling a cube — a completely different equation not covered by the theorem.

FAQ

Q: Do Diophantine equations always have integer solutions if the algebra "works out"? No. That is the whole point. $2x + 4y = 5$ is perfectly good algebra with infinitely many real solutions, but zero integer solutions because $\gcd(2,4)=2$ does not divide $5$.

Q: Is there a general method to solve every Diophantine equation? No — and this is a deep result. Hilbert's tenth problem (1900) asked for such an algorithm; Yuri Matiyasevich proved in 1970 that no general algorithm can exist. Linear equations are solvable algorithmically, but the general case is undecidable.

Q: Did Fermat really have a proof? Almost certainly not a correct general one. The mathematics needed for Wiles' proof did not exist in the 1600s. Fermat likely had an argument that worked for small exponents (he proved $n=4$) and mistakenly believed it generalized.

Q: Why does requiring $x, y \ge 0$ make coin problems harder? The general solution gives infinitely many integer answers, but only a finite window of $t$ values keeps both variables nonnegative — sometimes that window is empty. Finding it requires solving the inequalities, as in the $43$-cent example.

Q: What is the connection between the extended Euclidean algorithm and cryptography? In RSA you must find a number $d$ with $ed \equiv 1 \pmod{\varphi(n)}$ — that is, solve $ed - k\varphi(n) = 1$, a linear Diophantine equation. The extended Euclidean algorithm computes $d$ efficiently, which is why the same tool that makes change also protects your bank login.

Quick Revision

• A Diophantine equation seeks integer solutions to a polynomial equation.
• Linear: $ax + by = c$ has solutions iff $\gcd(a,b) \mid c$.
• General solution: $x = x_0 + \frac{b}{d}t$, $y = y_0 - \frac{a}{d}t$ where $d=\gcd(a,b)$, $t \in \mathbb{Z}$.
• Find $x_0, y_0$ via the extended Euclidean algorithm (Euclid then back-substitute).
• Pythagorean triples: $a=m^2-n^2$, $b=2mn$, $c=m^2+n^2$ generate all primitive triples.
• Fermat's Last Theorem: $x^n+y^n=z^n$ has no positive-integer solutions for $n\ge 3$; conjectured ~1637, proved by Wiles in 1994.
• No universal solving algorithm exists (Hilbert's tenth problem, Matiyasevich 1970).

Related Topics

Prerequisites

• Number Theory overview
• The Euclidean algorithm and greatest common divisors
• Basic modular arithmetic

Related Topics

• Modular arithmetic and the Chinese Remainder Theorem
• Prime numbers and factorization
• Pythagorean theorem (see the Geometry branch: ../../4._Geometry/index.md)

Next Topics

• Elliptic curves and their connection to cryptography
• Continued fractions and Pell's equation
• Integer programming (optimization over whole numbers)