Math Core

A Diophantine equation is an equation where only integer solutions count. There is no single method for all of them, but AIME problems almost always yield to one of a handful of moves: solve a linear equation with Bézout, factor (often with Simon's Favorite Factoring Trick), parametrize Pythagorean triples, rule out cases with a modulus, or recognize a Pell equation. This module teaches each move and when to reach for it.

Linear equations

Linear Diophantine equations

$ax + by = c$ has integer solutions if and only if $g = \gcd(a, b)$ divides $c$ . If $(x_0, y_0)$ is one solution, all solutions are

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

Why. Bézout's identity says $g = au + bv$ for some integers $u, v$ (the Euclidean algorithm run backward finds them), so if $g \mid c$ you can scale up to hit $c$ . Conversely $g$ divides the left side, so it must divide $c$ . For the general solution: if $ax + by = ax_0 + by_0$ , then $a(x - x_0) = b(y_0 - y)$ . Dividing by $g$ , $\frac{a}{g}(x - x_0) = \frac{b}{g}(y_0 - y)$ with $\frac ag, \frac bg$ coprime, so $\frac bg \mid x - x_0$ .

To count positive solutions, find one solution, write the general one, and count the values of $t$ that keep both variables in range.

Chicken McNugget theorem

The Frobenius number for two coins

If $a, b$ are coprime positive integers, the largest integer that is not of the form $ax + by$ with $x, y \ge 0$ is $ab - a - b$ . Exactly $\dfrac{(a-1)(b-1)}{2}$ positive integers are not representable.

Why. Any $n$ can be written $n = ax + by$ with a unique $y \in \{0, 1, \dots, a-1\}$ (choose $y$ with $by \equiv n \pmod a$ ). Then $n$ is representable with nonnegative coefficients exactly when this $x$ is $\ge 0$ , that is, $n \ge by$ . The largest failure takes $y = a - 1$ and $x = -1$ : $n = b(a-1) - a = ab - a - b$ . For the count, $n$ is representable iff $ab - a - b - n$ is not (for $0 \le n \le ab - a - b$ ), so exactly half of those $ab - a - b + 1 = (a-1)(b-1)$ numbers fail.

Factoring

If an equation has a product $xy$ and linear terms, complete the rectangle:

$xy + ax + by = c \iff (x + b)(y + a) = c + ab.$

This is Simon's Favorite Factoring Trick. The right side is a fixed number, so solutions correspond to its factor pairs. Count positive divisors and then check which factor pairs keep $x, y$ in range, including negative factor pairs.

The same idea handles differences of squares, $m^2 - n^2 = (m - n)(m + n)$ , where the two factors must have the same parity.

Worked example: Factoring trick

Find all positive integer solutions of $xy + 2x + 3y = 30$ .

Add $6$ : $(x + 3)(y + 2) = 36$ . With $x \ge 1$ , $y \ge 1$ we need $x + 3 \ge 4$ and $y + 2 \ge 3$ . Factor pairs of $36$ : $(4, 9), (6, 6), (9, 4), (12, 3)$ work, while $(18, 2)$ and $(36, 1)$ make $y \le 0$ . The solutions are $(x, y) = (1, 7), (3, 4), (6, 2), (9, 1)$ .

Pythagorean triples

All Pythagorean triples

Every primitive triple ( $\gcd = 1$ ) with $a^2 + b^2 = c^2$ and $b$ even has the form

$a = m^2 - n^2, \qquad b = 2mn, \qquad c = m^2 + n^2$

with $m > n \ge 1$ , $\gcd(m, n) = 1$ and $m - n$ odd. Every triple is $k$ times a primitive one.

Sketch. In a primitive triple exactly one leg is even; say $b$ . Then $b^2 = (c - a)(c + a)$ , and $\frac{c-a}{2}, \frac{c+a}{2}$ are coprime integers whose product is the square $\left(\frac b2\right)^2$ . Coprime numbers whose product is a square are both squares: $\frac{c+a}{2} = m^2$ , $\frac{c-a}{2} = n^2$ .

Often you don't even need the formula: with a known leg $a$ , write $a^2 = (c - b)(c + b)$ and count factor pairs of the same parity.

Worked example: Fixed perimeter

Find all right triangles with integer sides and perimeter $60$ .

The perimeter of $k(m^2 - n^2, 2mn, m^2 + n^2)$ is $2km(m+n)$ , so $km(m + n) = 30$ with $m < m + n < 2m$ . Try $(m, n) = (2, 1)$ : $m(m+n) = 6$ , $k = 5$ , giving $(15, 20, 25)$ . Try $(3, 2)$ : $15$ , $k = 2$ , giving $(10, 24, 26)$ . Other pairs have $m(m + n) = 12, 20, 28, 30, \dots$ that either don't divide $30$ or break the conditions ( $(5, 1)$ has $m - n$ even). So there are exactly two triangles.

Ruling out solutions with a modulus

To show an equation has no solutions, reduce it modulo something where squares (or cubes, or powers) take few values. Good moduli: $4$ and $8$ for squares ( $x^2 \equiv 0, 1, 4 \pmod 8$ ), $9$ or $7$ for cubes, $3$ , $5$ , $16$ .

Worked example: No solutions

Show that $x^2 - 3y^2 = 2026$ has no integer solutions.

Mod $4$ : $x^2 - 3y^2 \equiv x^2 + y^2$ , and $2026 \equiv 2$ , so $x$ and $y$ are both odd. Then mod $8$ : $x^2 \equiv y^2 \equiv 1$ , so $x^2 - 3y^2 \equiv -2 \equiv 6$ . But $2026 \equiv 2 \pmod 8$ . Contradiction.

Pell equations

For a non-square $D$ , the equation $x^2 - Dy^2 = 1$ has infinitely many positive solutions. If $(x_1, y_1)$ is the smallest, all of them come from

$x_k + y_k\sqrt D = \left(x_1 + y_1\sqrt D\right)^k.$

The reason: $(x^2 - Dy^2)$ is multiplicative in the sense that the "norm" of a product equals the product of norms, so powers of a solution are solutions. (That these are all the solutions takes more work; you can quote it.) For $x^2 - 2y^2 = 1$ , starting from $3 + 2\sqrt2$ : $(3 + 2\sqrt2)^2 = 17 + 12\sqrt2$ , then $99 + 70\sqrt2$ , and so on.

Common mistake

When counting factor pairs, don't forget negative pairs and don't forget parity. For $(x - 6)(y - 4) = N$ , both factors could be negative; check whether that's consistent with $x, y \ge 1$ . For $m^2 - n^2 = N$ , the factors $m - n$ and $m + n$ must both be even or both odd.