Math Core

A Diophantine equation is an equation where only integer solutions count. The linear ones, $ax + by = c$ , show up on the AMC as ticket sales, coin and stamp problems, and "how many ways" questions. You need three skills: decide whether there are any solutions, write down all of them, and count the ones that fit the constraints (usually positive or nonnegative).

When are there solutions?

Whatever integers $x$ and $y$ you pick, $ax + by$ is a multiple of $g = \gcd(a, b)$ . So if $g \nmid c$ there are no solutions. The converse is also true (it follows from the Euclidean algorithm, in the next module): $ax + by = c$ has integer solutions exactly when $\gcd(a, b)$ divides $c$ . For example, $6x + 15y = 40$ has none, because every value of $6x + 15y$ is a multiple of $3$ .

All solutions from one

Suppose $\gcd(a, b) = 1$ and $(x_0, y_0)$ is one solution. If $(x, y)$ is another, subtracting gives $a(x - x_0) = -b(y - y_0)$ . Since $a$ and $b$ share no factor, $b$ must divide $x - x_0$ . That forces the following.

General solution

If $\gcd(a, b) = 1$ and $(x_0, y_0)$ is one solution of $ax + by = c$ , then every solution is

$x = x_0 + bt, \qquad y = y_0 - at, \qquad t \text{ an integer}.$

Solutions step by $b$ in $x$ and by $a$ in $y$ (in opposite directions). If $\gcd(a, b) = g \gt 1$ , divide the whole equation by $g$ first.

To find one solution, use congruences: $ax + by = c$ forces $by \equiv c \pmod a$ . Solve for $y$ modulo $a$ , then compute $x$ .

Counting solutions with constraints

Once you have the general solution, the constraints $x \ge 0$ (or $x \gt 0$ ) and $y \ge 0$ become two inequalities on $t$ , and you count the integers in between. Often it's quicker to say " $y$ must be $\equiv r \pmod a$ " and list the values of $y$ directly.

The Chicken McNugget theorem

Which amounts can you make from $a$ -cent and $b$ -cent coins, using nonnegative numbers of each?

Chicken McNugget theorem

If $a$ and $b$ are relatively prime positive integers, the largest integer that cannot be written as $ax + by$ with $x, y \ge 0$ is

$ab - a - b,$

and exactly $\dfrac{(a-1)(b-1)}{2}$ positive integers cannot be written that way.

Why: every integer $n$ has exactly one representation $n = ax + by$ with $0 \le y \le a - 1$ . It uses nonnegative coins exactly when that $x \ge 0$ . The worst case is $y = a - 1$ and $x = -1$ , which gives $n = -a + b(a - 1) = ab - a - b$ . Every larger $n$ has $x \ge 0$ . For the count, $n$ and $ab - a - b - n$ can't both be representable (they would add to $ab - a - b$ ) and one of them always is, so exactly half of $0, 1, \dots, ab - a - b$ fail.

With three or more coin values there is no formula. List which residues you can reach modulo the smallest coin, and the smallest amount reaching each.

Worked example: Finding every solution

Find all positive integer solutions of $7x + 11y = 100$ .

Mod $7$ : $11y \equiv 100$ , that is $4y \equiv 2 \pmod 7$ . Try $y = 4$ : $16 \equiv 2$ . So $y \equiv 4 \pmod 7$ . With $y = 4$ , $7x = 56$ and $x = 8$ .

The general solution is $x = 8 - 11t$ , $y = 4 + 7t$ . For $x \gt 0$ you need $t \le 0$ ; for $y \gt 0$ you need $t \ge 0$ . So $t = 0$ and the only positive solution is $(8, 4)$ .

Worked example: Counting nonnegative solutions

How many ordered pairs of nonnegative integers $(x, y)$ satisfy $3x + 5y = 100$ ?

Mod $3$ : $5y \equiv 100$ , so $2y \equiv 1$ and $y \equiv 2 \pmod 3$ . Also $5y \le 100$ , so $y \le 20$ . The values $y = 2, 5, 8, 11, 14, 17, 20$ each give a nonnegative integer $x$ . There are $7$ solutions.

Worked example: Coins that can't make change

Coins come in $6$ -cent and $11$ -cent values. What is the largest amount you can't pay exactly, and how many positive amounts can't be paid?

$\gcd(6, 11) = 1$ , so the largest impossible amount is $6 \cdot 11 - 6 - 11 = 49$ cents, and the number of impossible positive amounts is $\dfrac{5 \cdot 10}{2} = 25$ .

Worked example: A three-variable count

In how many ways can you make $20$ cents from pennies, $2$ -cent coins and nickels?

You need nonnegative $x + 2y + 5z = 20$ . Fix $z$ and count solutions of $x + 2y = 20 - 5z$ , which has $\left\lfloor \dfrac{20 - 5z}{2} \right\rfloor + 1$ solutions:

$z$	$20 - 5z$	solutions
$0$	$20$	$11$
$1$	$15$	$8$
$2$	$10$	$6$
$3$	$5$	$3$
$4$	$0$	$1$

The total is $29$ .

Common mistake

Read the constraints carefully. "Positive" means $x, y \ge 1$ ; "nonnegative" allows $0$ . The Chicken McNugget formula is for nonnegative combinations. If both kinds of coin must be used at least once, the amounts shift up by $a + b$ .

Practice

Practice 1

Which of the following equations has no solution in integers $x$ and $y$ ?

Practice 2

How many ordered pairs of positive integers $(x, y)$ satisfy $4x + 7y = 150$ ?

Enter a number. Fractions like 3/4 and sqrt(2) are OK.

Practice 3

Using only $7$ -point and $9$ -point scoring plays, what is the largest score a team can not reach?

Practice 4

A theater sold adult tickets for $11 each and child tickets for $7 each, taking in exactly $200. At least one of each kind was sold. What is the greatest possible total number of tickets sold?

Enter a number. Fractions like 3/4 and sqrt(2) are OK.

Practice 5

How many positive integers can not be written in the form $5a + 8b$ with $a$ and $b$ nonnegative integers?

Practice 6

Stamps come in $13$ -cent and $17$ -cent values. In how many ways (counting only how many of each stamp you use) can you make exactly $10.00 of postage?

Enter a number. Fractions like 3/4 and sqrt(2) are OK.

Practice 7

A snack bar sells boxes of $8$ , $12$ and $15$ nuggets. How many positive whole numbers of nuggets can not be bought exactly?

Enter a number. Fractions like 3/4 and sqrt(2) are OK.

Real contest practice

2023 AMC 12B, Problem 16: the largest price that can't be paid with three coin values.
2019 AIME II, Problem 14: a harder stamp problem built on the Chicken McNugget theorem (a stretch beyond the AMC).