The last number you can't make

Pick two whole numbers a and b that share no common factor bigger than 1. Using copies of a and copies of b — as many of each as you like — which totals c = x·a + y·b can you build? We show two things: every number bigger than ab can be built, and the number ab − a − b never can.

Play with it

value a4

value b7

biggest shared factor: 1 biggest you can't build: ab−a−b = 17 can't build in total: (a−1)(b−1)/2 = 9

a and b share a common factor — so the theorem no longer applies. Every total x·a + y·b is a multiple of that shared factor, so the orange gaps now go on forever. There is no last gap. This is exactly why we need a and b to share no common factor.

can be built can't be built ab − a − b

Hover or tap a dot to see how to build that number.

The claim, precisely

Theorem

Let a and b be positive whole numbers that share no common factor bigger than 1.

Part 1. Every whole number c > ab can be built as c = x·a + y·b, using whole-number counts x, y ≥ 0.

Part 2. The number ab − a − b cannot be built this way.

Play with the sliders above and the picture is always the same: a scatter of orange numbers you can't build, then a sharp cutoff, then solid blue (buildable) forever. The proof explains both why the cutoff exists (Part 1) and exactly where it sits (Part 2).

Part 1 — everything past ab is reachable

Step 1 · one solution always exists (but it may cheat)

Here's a standard fact about two numbers that share no common factor: you can always combine them to land on exactly 1, using whole-number multipliers u and v (usually one of them is negative). Written out:

u·a + v·b = 1.

Now multiply both sides by c. That scales the combination up from 1 to c:

x₀·a + y₀·b = c, where x₀ = u·c and y₀ = v·c.

So there is always some way to hit c with whole numbers. The catch: because u or v was negative, x₀ or y₀ can come out negative too — and a negative count doesn't correspond to actually building c. The whole job now is to turn this into a solution where both counts are ≥ 0.

Step 2 · all the solutions form an evenly spaced ladder

Say we have two solutions, x·a + y·b = c and x₀·a + y₀·b = c. Subtract one from the other:

(x − x₀)·a = (y₀ − y)·b.

The right side is a multiple of b, so the left side is a multiple of b too. But a shares no common factor with b, so a can't supply any part of that multiple of b — it has to come entirely from (x − x₀). In other words, (x − x₀) is itself a multiple of b. Write it as t·b; putting that back in gives (y₀ − y) = t·a. So every solution looks like

x = x₀ + t·b, y = y₀ − t·a, for any whole number t,

and every choice of t really is a solution. So the solutions form a ladder: pick any one, then step t up or down. Each step adds b to x and subtracts a from y — and the total never changes, since (+b)·a + (−a)·b = 0.

The ladder of solutions, drawn

How to read this picture:

Each dot is one solution — a pair of counts (x, y) with x·a + y·b = c. Its left–right position is x, its up–down position is y.
From Step 2 the dots lie on a straight line, evenly spaced: each step to the right adds b to x and drops a from y (the orange arrow).
We only actually build c when a dot sits in the blue shaded region, where both counts are ≥ 0. Dots outside it use a negative count — a cheat.
The dashed strip holds the choices with x between 0 and b − 1. Because the dots are exactly b apart left-to-right, exactly one dot lands inside it (circled).

Now drag c. While c is small, the circled dot sits below the shaded region — its y is negative, so c can't be built. As c grows past ab, the circled dot rises into the shaded region and c becomes buildable. That single moment is Part 1.

target total c29

Step 3 · pick the solution in the strip, then check its height

Stepping along the ladder shifts x by b each time, so exactly one rung lands in the strip

0 ≤ x ≤ b − 1.

Pick that one. It already has x ≥ 0. We just need to check its y is also ≥ 0. Rearrange the equation to y·b = c − x·a. Since x is at most b − 1, we subtract at most (b − 1)a; and we're told c > ab. Chaining those:

y·b = c − x·a ≥ c − (b − 1)a > ab − (b − 1)a = a > 0.

So y·b is positive, and since b is positive, y is positive too. Both counts are ≥ 0, so we have genuinely built c = x·a + y·b.

In one sentence: among all the solutions, take the one whose x is smallest but still ≥ 0 (so under b). Then x·a uses up less than ab of the total, and since c is bigger than ab, there is a positive amount left over for y·b — so y is positive too.

Part 2 — why ab − a − b is impossible

Step 1 · suppose you could, then rearrange

Suppose the opposite of what we want to prove: that you can build it, say ab − a − b = x·a + y·b with counts x, y ≥ 0. Add a and b to both sides and group the terms:

ab = (x + 1)·a + (y + 1)·b.

This rearrangement is the whole trick. The two multipliers x + 1 and y + 1 are now both at least 1 (because x, y ≥ 0) — keep that in mind.

Step 2 · compare remainders, dividing first by a, then by b

Look at both sides of ab = (x + 1)·a + (y + 1)·b and ask for their remainder after dividing by a:

The left side ab is a times b, a multiple of a — remainder 0.
The term (x + 1)·a is also a multiple of a — remainder 0.
So the remaining term (y + 1)·b must have remainder 0 as well — that is, a divides (y + 1)·b.

But a shares no common factor with b, so the factor of a can't come from b — it must come from (y + 1). So a divides (y + 1). And y + 1 is at least 1, so it is a positive multiple of a, which forces y + 1 ≥ a.

Running the exact same argument, but dividing by b instead, gives the mirror result: x + 1 ≥ b.

Step 3 · the two pieces are already too big

Put those two facts — x + 1 ≥ b and y + 1 ≥ a — back into ab = (x + 1)·a + (y + 1)·b:

ab = (x + 1)·a + (y + 1)·b ≥ b·a + a·b = 2ab.

So ab ≥ 2ab, which means ab ≤ 0 — impossible, since a and b are positive. Our supposition was wrong, so ab − a − b can't be built.

The picture behind it all

Here is the same number line, folded into columns: each column collects the numbers that leave the same remainder when divided by a. Moving up one cell adds a. So the moment a column contains any number you can build, everything above it in that column can be built too — just add another a.

What is the lowest buildable number in each column — the "key" that unlocks it? The multiples of b: 0, b, 2b, …, (a−1)b. Because a and b share no common factor, these a multiples all leave different remainders when divided by a — so they land in a different columns, one key per column.

can be built gap multiple of b (unlocks its column) ab − a − b

Now both halves of the theorem are visible at once. The last column to unlock is the one opened by the biggest key, (a − 1)·b = ab − b. The cell one step (one a) below that key is

(ab − b) − a = ab − a − b,

the highest number you can't build anywhere on the board — exactly the number Part 2 ruled out. And every number above ab − b sits above its column's key, so it can be built; in particular everything past ab can, which is Part 1 again, with room to spare.

Why a and b must share no factor: set the sliders to something like a = 6, b = 9 (both divisible by 3). Now the multiples of b keep landing in the same few columns and never reach the rest — those columns stay orange forever, so there is no last gap at all.