Diophantine equation

In mathematics, a Diophantine equation is a polynomial equation with integer coefficients, for which only integer solutions are of interest. A linear Diophantine equation equates the sum of two or more unknowns, with coefficients, to a constant. An exponential Diophantine equation is one in which unknowns can appear in exponents.

Diophantine problems have fewer equations than unknowns and involve finding integers that solve all equations simultaneously. Because such systems of equations define algebraic curves, algebraic surfaces, or, more generally, algebraic sets, their study is a part of algebraic geometry that is called Diophantine geometry.

The word Diophantine refers to the Hellenistic mathematician of the 3rd century, Diophantus of Alexandria, who made a study of such equations and was one of the first mathematicians to introduce symbolism into algebra. The mathematical study of Diophantine problems that Diophantus initiated is now called Diophantine analysis.

While individual equations present a kind of puzzle and have been considered throughout history, the formulation of general theories of Diophantine equations, beyond the case of linear and quadratic equations, was an achievement of the twentieth century.

In the following Diophantine equations, w, x, y, and z are the unknowns and the other letters are given constants:

The simplest linear Diophantine equation takes the form $${\displaystyle ax+by=c,}$$ where a, b and c are given integers. The solutions are described by the following theorem:

Proof: If d is this greatest common divisor, Bézout's identity asserts the existence of integers e and f such that ae + bf = d. If c is a multiple of d, then c = dh for some integer h, and (eh, fh) is a solution. On the other hand, for every pair of integers x and y, the greatest common divisor d of a and b divides ax + by. Thus, if the equation has a solution, then c must be a multiple of d. If a = ud and b = vd, then for every solution (x, y), we have $${\displaystyle {\begin{aligned}a(x+kv)+b(y-ku)&=ax+by+k(av-bu)\\&=ax+by+k(udv-vdu)\\&=ax+by,\end{aligned}}}$$ showing that (x + kv, y − ku) is another solution. Finally, given two solutions such that $${\displaystyle ax_{1}+by_{1}=ax_{2}+by_{2}=c,}$$ one deduces that $${\displaystyle u(x_{2}-x_{1})+v(y_{2}-y_{1})=0.}$$ As u and v are coprime, Euclid's lemma shows that v divides x₂ − x₁, and thus that there exists an integer k such that both $${\displaystyle x_{2}-x_{1}=kv,\quad y_{2}-y_{1}=-ku.}$$ Therefore, $${\displaystyle x_{2}=x_{1}+kv,\quad y_{2}=y_{1}-ku,}$$ which completes the proof.

The Chinese remainder theorem describes an important class of linear Diophantine systems of equations: let ${\displaystyle n_{1},\dots ,n_{k}}$ be k pairwise coprime integers greater than one, ${\displaystyle a_{1},\dots ,a_{k}}$ be k arbitrary integers, and N be the product ${\displaystyle n_{1}\cdots n_{k}.}$ The Chinese remainder theorem asserts that the following linear Diophantine system has exactly one solution ${\displaystyle (x,x_{1},\dots ,x_{k})}$ such that 0 ≤ x < N, and that the other solutions are obtained by adding to x a multiple of N: $${\displaystyle {\begin{aligned}x&=a_{1}+n_{1}\,x_{1}\\&\;\;\vdots \\x&=a_{k}+n_{k}\,x_{k}\end{aligned}}}$$