Diophantine Equation

6 min read#number-theory

An equation whose solutions must be whole numbers — solvable in the linear case exactly when the gcd of the coefficients divides the constant.

Contents

Diophantine Equation

A Diophantine equation is a polynomial equation for which we demand integer solutions — no fractions, no decimals, just whole numbers. Named for Diophantus of Alexandria (c. 250 AD), they are among the oldest and hardest objects in mathematics. The constraint "integers only" changes everything: an equation with infinitely many real solutions may have none at all in integers, or exactly one, or a whole lattice of them.

The linear case is completely solved

The simplest family is the linear Diophantine equation in two unknowns:

ax + by = c.

Geometrically this is a straight line; we are asking which of its points land on the integer grid. The answer is a clean theorem resting entirely on the Greatest Common Divisor:

So 6x + 9y = 21 is solvable because \gcd(6,9) = 3 divides 21; but 6x + 9y = 20 has no integer solution, since the left side is always a multiple of 3 and 20 is not.

The lattice of solutions

When solutions exist, there are infinitely many, evenly spaced along the line. If (x_0, y_0) is one solution, the rest are

x = x_0 + \frac{b}{g}t, \qquad y = y_0 - \frac{a}{g}t, \qquad t \in \mathbb{Z}.

The integer points sit at regular intervals — a one-dimensional lattice marching along the line. The sketch shows which lines catch grid points and which slip between them entirely.

The line ax + by = c over the integer grid. Green dots are integer solutions, evenly spaced along the line. Drag left↔right to change c: when gcd(a,b) divides c the line threads through lattice points; otherwise it weaves between them with none.

Beyond linear: a different universe

Raise the degree and the difficulty explodes. Pythagorean triples solve x^2 + y^2 = z^2 and form an infinite, beautifully structured family (3,4,5; 5,12,13; …). But change the exponent and everything breaks:

There is no general algorithm that can decide whether an arbitrary Diophantine equation has solutions — this is the negative answer to Hilbert's tenth problem. The linear case we solved completely is the calm shore of an ocean that quickly becomes unfathomable.

Pythagorean triples: hypotenuse of x² + y² = z²
Integer solutions of x² + y² = z² form an infinite structured family — yet the moment the exponent passes 2, Fermat's Last Theorem says the integer solutions vanish entirely.

Does the equation 4x + 6y = 9 have any integer solutions?

See also

Related topics

  • Greatest Common DivisorThe largest integer dividing two numbers, found in a handful of steps by Euclid's algorithm of repeated remainders.
  • Continued FractionA representation of a real number as a nested stack of fractions, yielding the best possible rational approximations.
  • Number TheoryThe study of the integers — primes, divisibility, and congruence — whose oldest puzzles became the foundation of modern cryptography.
  • Fundamental Theorem of ArithmeticEvery integer greater than 1 is a product of primes in exactly one way, up to the order of the factors.
  • Euler's Totient Functionφ(n) counts the integers from 1 to n that share no factor with n — the size of the group of units that powers RSA.
  • RSAPublic-key encryption and signatures built on the difficulty of factoring a product of two large primes.

Referenced by