Mathematics.

elementary number theory

Diophantine Equations

Number Theory30 minDifficulty4 out of 10

You should know: gcd and lcm

Overview

A Diophantine equation is a polynomial equation, named after the 3rd-century Alexandrian mathematician Diophantus, for which only integer (or sometimes rational) solutions are sought. The simplest and most important family is the linear Diophantine equation ax + by = c in two unknowns: a complete theory tells you exactly when solutions exist and how to list all of them, using nothing more than the Euclidean algorithm. By Bézout's identity, gcd(a, b) always divides ax + by for any integers x, y, so ax + by = c has an integer solution precisely when gcd(a, b) divides c — and if one solution is found, every other solution is obtained by shifting x and y by multiples of b/gcd(a,b) and a/gcd(a,b) respectively. Beyond the linear case, Diophantine equations range from the tractable (Pythagorean triples x² + y² = z²) to the notoriously hard (Fermat's Last Theorem xⁿ + yⁿ = zⁿ, unsolved for over 350 years) and even the undecidable (Hilbert's tenth problem showed no general algorithm can decide solvability).

Intuition

Think of ax + by as every value reachable by combining a-step and b-step jumps (positively or negatively) on the number line. The set of all reachable values is exactly the multiples of gcd(a, b) — this is Bézout's identity. So c is reachable if and only if it's a multiple of gcd(a, b). Once you find one way to reach c (via the extended Euclidean algorithm), you can always trade b/gcd(a,b) worth of x-steps for a/gcd(a,b) worth of y-steps and land on c again, which is exactly the family of all solutions.

Formal Definition

Definition

For integers a, b, c with a, b not both zero, the linear Diophantine equation is:

ax+by=c,x,y∈Zax + by = c, \qquad x, y \in \mathbb{Z}
Linear Diophantine equation
ax+by=c has a solution  ⟺  gcd⁡(a,b)∣cax + by = c \text{ has a solution} \iff \gcd(a,b) \mid c
Solvability criterion
(x0,y0) a solution ⇒ (x0+tbgcd⁡(a,b), y0−tagcd⁡(a,b)), t∈Z(x_0, y_0) \text{ a solution} \ \Rightarrow\ \left(x_0 + t\tfrac{b}{\gcd(a,b)},\ y_0 - t\tfrac{a}{\gcd(a,b)}\right), \ t \in \mathbb{Z}
General solution family

Worked Examples

  1. Run the Euclidean algorithm on 172 and 20.

    172=8⋅20+12172 = 8\cdot 20 + 12

  2. Continue reducing.

    20=1⋅12+820 = 1\cdot 12 + 8

  3. Continue reducing.

    12=1⋅8+412 = 1\cdot 8 + 4

  4. Remainder reaches 0, so gcd(172, 20) = 4. Since 4 | 8, a solution exists.

    8=2⋅4+08 = 2\cdot 4 + 0

  5. Back-substituting the steps (extended Euclidean algorithm) gives 172(2) + 20(−17) = 4; multiply both sides by 8/4 = 2.

    172(4)+20(−34)=8172(4) + 20(-34) = 8

Answer: Yes: (x, y) = (4, −34) is one solution, since 172·4 + 20·(−34) = 688 − 680 = 8.

Practice Problems

Difficulty 3/10

Does 6x + 10y = 14 have an integer solution? Justify using gcd(6, 10).

Difficulty 3/10

Explain why 6x + 9y = 4 has no integer solutions.

Difficulty 6/10

A vending machine accepts only 3-unit and 5-unit tokens. Which nonnegative combinations make exactly 11 units? (Give one solution with x, y ≥ 0.)

Quiz

The equation ax + by = c has an integer solution if and only if:
Given one solution (x₀, y₀) to ax + by = c, every other integer solution has the form:
Which of these is a famous nonlinear Diophantine equation that resisted proof for over 350 years?

Summary

  • A linear Diophantine equation ax + by = c has integer solutions iff gcd(a, b) divides c (Bézout's identity).
  • One solution is found via the extended Euclidean algorithm; all solutions form a family shifted by multiples of b/gcd(a,b) and a/gcd(a,b).
  • Nonlinear Diophantine equations range from tractable (Pythagorean triples) to famously hard (Fermat's Last Theorem) to undecidable in general (Hilbert's tenth problem).

References

  1. WebsiteWikipedia — Diophantine equation