Diophantine equations

A Diophantine equation is a polynomial equation with integer coefficients for which we seek integer solutions only. Named for the third-century Greek mathematician Diophantus of Alexandria, these problems ask a more restrictive question than ordinary algebra: 3x + 5y = 47 has infinitely many real solutions, but only a handful where both x and y are nonnegative integers.

The most common type is the linear Diophantine equation ax + by = c. Such an equation has integer solutions exactly when the greatest common divisor of a and b divides c. For example, 6x + 9y = 20 has no integer solutions because gcd(6, 9) = 3 does not divide 20, while 6x + 9y = 21 has infinitely many: once one solution is found, all others follow by shifting x by b/gcd(a, b) and y by −a/gcd(a, b).

Competition problems dress these equations in word-problem clothing — counting how many ways to make an exact amount with two coin or ticket denominations, or splitting objects into groups of fixed sizes. Useful techniques include checking divisibility, working modulo one of the coefficients to pin down residues, factoring tricks such as Simon's Favorite Factoring Trick for equations like xy + 3x + 2y = 12, and bounding the variables to make a finite search.

The AMC 8, AMC 10/12, and other math competitions test Diophantine equations as a core number theory topic. Know the gcd solvability condition, be comfortable using modular arithmetic to narrow candidates, and practice translating word problems about whole-number quantities into equations.