Diophantine Equations

Diophantine equations are equations where we seek integer (or sometimes rational) solutions. Typical olympiad problems ask you to decide whether integer solutions exist, to find all solutions, or to show there are only finitely many.

Warm-up examples

• Linear: solve $ax + by = c$ in integers.
• Quadratic: solve $x^2 - Dy^2 = 1$ (Pell-type).
• Congruence-flavoured: decide if $x^2 + y^2 = z^2$ has solutions with extra conditions.

Linear Diophantine equations

The equation $ax + by = c$ has an integer solution iff $\gcd(a,b) \mid c$. If $(x_0,y_0)$ is one solution and $g=\gcd(a,b)$, then all solutions are

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

This “one solution + parametrise” pattern shows up constantly.

Core techniques (what to try first)

Modular obstructions

Reduce the equation mod $m$ to rule out solutions. Classic facts:

• Squares mod $4$ are $0$ or $1$.
• Squares mod $8$ are $0,1,4$.
• Mod $3$, squares are $0$ or $1$.

Bounding / size arguments

Use inequalities to show there can only be finitely many possibilities, then check them.

Factorisations

Rewrite as a product:

$$x^2 - y^2 = (x-y)(x+y)$$

or use unique factorisation in $\mathbb Z$ to constrain possibilities.

Infinite descent

Assume a solution exists and build a smaller one repeatedly, contradicting well-ordering.

Vieta jumping (special but powerful)

For quadratic-in-each-variable forms like $x^2 + y^2 = kxy + c$, use the fact that if $(x,y)$ is a solution then so is $(x, ky - x)$, allowing you to “jump” to smaller solutions until you reach a base case.

What you should take away

Most Diophantine problems are about finding a structure that forces integrality: a gcd condition, a congruence class, a factorisation, or a descent step. Try to identify which of these is “built in” to the equation.