Diophantine Equations

A Diophantine equation is a polynomial equation, usually involve two or more unknowns, such that only the integer (or rational) solutions are sought. The field is named after Diophantus of Alexandria, who first studied these problems systematically. Diophantine analysis explores whether solutions exist, and if so, how many and how to find them.

Linear Diophantine Equations

The simplest Diophantine equation is the linear form in two variables: $ax+by=c$ where $a,b,c$ are given integers.

Criteria for Solvability

A linear Diophantine equation has an integer solution if and only if $\gcd (a,b)$ divides $c$.

• If $d=\gcd (a,b)$ and $d\mid c$, there are infinitely many solutions.
• If $(x_0,y_0)$ is a particular solution (found via the Extended Euclidean Algorithm), the general solution is: $x=x_0+k\frac{b}{d},y=y_0-k\frac{a}{d}$ for any integer $k$.

Pythagorean Triples

A classic non-linear Diophantine equation is $x^2+y^2=z^2$. A primitive Pythagorean triple is a set of integers $(x,y,z)$ such that $\gcd (x,y,z)=1$ and they satisfy the equation. Euclid’s formula generates all primitive triples: $x=m^2-n^2,y=2mn,z=m^2+n^2$ where $m>n>0$, $\gcd (m,n)=1$, and $m,n$ have opposite parity.

Pell’s Equation

Pell’s equation is of the form: $x^2-D{y}^2=1$ where $D$ is a positive non-square integer.

• The equation always has the trivial solution $(1,0)$.
• It has infinitely many positive integer solutions.
• Solutions are found using the continued fraction expansion of $\sqrt{D}$. If $p_k/q_k$ are the convergents of the continued fraction, then for some $k$, $(p_k,q_k)$ will satisfy the equation.

Fermat’s Last Theorem (FLT)

Perhaps the most famous problem in the history of mathematics, FLT states that the Diophantine equation: $x^n+y^n=z^n$ has no non-zero integer solutions for $n>2$. Proposed by Pierre de Fermat in 1637, it remained unproven for over 350 years until Andrew Wiles provided a proof in 1994. The proof involved extremely deep connections between elliptic curves and modular forms (the Taniyama-Shimura-Weil conjecture).

Elliptic Curves

An elliptic curve is a cubic Diophantine equation of the form: $y^2=x^3+ax+b$ The rational points on an elliptic curve form an abelian group under a specific “chord-and-tangent” addition law.

• Mordell-Weil Theorem: The group of rational points on an elliptic curve is finitely generated.
• This means all rational points can be derived from a finite set of “generator” points.

Hilbert’s Tenth Problem

In 1900, David Hilbert challenged mathematicians to find an algorithm that could determine, in a finite number of steps, whether any given Diophantine equation has integer solutions.

• Matiyasevich’s Theorem (1970): Showed that no such algorithm exists. The problem is undecidable. This result proves that Diophantine equations are powerful enough to simulate any Turing machine.

Thue’s Theorem and Boundedness

For higher-degree equations of the form $f(x,y)=c$ where $f$ is a homogeneous irreducible polynomial of degree $\ge 3$, Axel Thue proved that there are only finitely many integer solutions. This was a major result in the theory of Diophantine Approximation, which studies how closely irrational numbers can be approximated by rationals.

Python: Finding Pythagorean Triples

def generate_pythagorean_triples(limit):
    triples = []
    for m in range(2, int(limit**0.5) + 1):
        for n in range(1, m):
            if (m - n) % 2 == 1 and math.gcd(m, n) == 1:
                x = m*m - n*n
                y = 2*m*n
                z = m*m + n*n
                if z <= limit:
                    triples.append((x, y, z))
    return triples

Exercise