Maths WorkshopMaths problems with full solutions
Exercise 1338Number theory › Diophantine equationsOlympiadAdded 5 Nov 2026

The Frobenius coin problem for two coins

#Frobenius number#linear Diophantine#Chicken McNugget

Statement

Let a,ba,b be coprime positive integers. Prove that ab−a−bab-a-b cannot be written as ax+byax+by with integers x,y≥0x,y\ge0, but every integer n>ab−a−bn>ab-a-b can.

Hint

Given nn, choose the representation n=ax+byn=ax+by in which 0≤x≤b−10\le x\le b-1. When is y≥0y\ge0?

Show solutionHide solution

Solution

Normalising. Since gcd⁡(a,b)=1\gcd(a,b)=1, aa is invertible modulo bb, so for each integer nn there is a unique x0∈{0,…,b−1}x_0\in\{0,\dots,b-1\} with ax0≡n(modb)ax_0\equiv n\pmod b. Put y0=n−ax0b∈Zy_0=\frac{n-ax_0}b\in\mathbb Z. Every integer solution of ax+by=nax+by=n is (x0+tb, y0−ta)(x_0+tb,\ y_0-ta) for t∈Zt\in\mathbb Z.

Criterion. nn is representable with x,y≥0x,y\ge0 iff y0≥0y_0\ge0. Indeed, a representation needs x0+tb≥0x_0+tb\ge0, which forces t≥0t\ge0, and then y0−ta≤y0y_0-ta\le y_0 must be ≥0\ge0, so y0≥0y_0\ge0. Conversely y0≥0y_0\ge0 gives the representation (x0,y0)(x_0,y_0).

The number n=ab−a−bn=ab-a-b. We need ax0≡−a−b≡−a(modb)ax_0\equiv-a-b\equiv-a\pmod b, so x0≡−1x_0\equiv-1, i.e. x0=b−1x_0=b-1. Then y0=ab−a−b−a(b−1)b=−bb=−1<0y_0=\frac{ab-a-b-a(b-1)}b=\frac{-b}b=-1<0. Not representable.

Larger nn. If n>ab−a−bn>ab-a-b, then since x0≤b−1x_0\le b-1,
y0=n−ax0b≥n−a(b−1)b>ab−a−b−ab+ab=−1,y_0=\frac{n-ax_0}b\ge\frac{n-a(b-1)}b>\frac{ab-a-b-ab+a}b=-1,
so y0>−1y_0>-1, and being an integer, y0≥0y_0\ge0.

Example. For a=5a=5, b=7b=7 the largest amount that cannot be paid is 35−12=2335-12=23.

Lesson. Reduce one variable modulo the other coefficient to get a canonical representative, then the sign of the other variable decides everything.