Kvant Math Problem 194

Take a small example, say $a=3$, $b=7$.

kvantmathematicsolympiad

Verified: no
Verdicts: UNKNOWN + UNKNOWN
Solve time: 10m04s
Source on kvant.digital

Problem

Two coprime positive integers $a$ and $b$ are given. It is known that every integer can be represented in the form $ax+by$, where $x$ and $y$ are integers. Consider the set $M$ of integers that can be represented in the form $ax+by$, where $x$ and $y$ are nonnegative integers.

  1. What is the largest number $c$ that does not belong to the set $M$?
  2. Prove that of the two numbers $n$ and $c-n$ (where $n$ is any integer), one belongs to $M$ and the other does not.

(In Figure 2, for $a=3$ and $b=7$, the integer points belonging to the set $M$ are shown in red, and those not belonging to it are shown in blue.)

Figure 2

A. A. Kirillov

Exploration

Take a small example, say $a=3$, $b=7$. The numbers representable as $3x+7y$ with $x,y\ge0$ begin

$$0,3,6,7,9,10,12,13,14,\ldots$$

The missing positive integers are

$$1,2,4,5,8,11.$$

The largest missing number is $11=3\cdot7-3-7$.

This suggests the classical Frobenius number $ab-a-b$.

To understand why, consider all integers of the form

$$c-k,\qquad c=ab-a-b.$$

Then

$$c-k=(a-1)(b-1)-1-k.$$

A useful observation is that every integer has a unique residue modulo $a$. Since $b$ is coprime to $a$, the residues

$$0,b,2b,\ldots,(a-1)b$$

are all distinct modulo $a$. Hence every integer $n$ can be written uniquely as

$$n\equiv jb \pmod a, \qquad 0\le j\le a-1.$$

Write

$$n=jb+qa.$$

Then $n\in M$ exactly when $q\ge0$, because $j$ is already nonnegative.

For the special number $c=ab-a-b$,

$$c-n=(a-1-j)b+(-1-q)a.$$

The coefficients differ from those of $n$ in a very symmetric way. If $q\ge0$, then $n\in M$, while the coefficient of $a$ in the displayed representation of $c-n$ equals $-1-q<0$, suggesting that $c-n\notin M$. Conversely, if $q<0$, then perhaps $c-n\in M$.

The delicate point is proving that the displayed representation is the unique representation with $0\le j\le a-1$. Without uniqueness, a negative coefficient in one representation would not exclude membership in $M$.

The core insight is thus the unique decomposition

$$n=jb+qa,\qquad 0\le j\le a-1,$$

and the symmetry

$$c-n=(a-1-j)b+(-1-q)a.$$

Problem Understanding

We are given coprime positive integers $a$ and $b$. Let

$$M={ax+by:x,y\in\mathbb Z_{\ge0}}.$$

We must determine the largest integer not belonging to $M$, and prove a symmetry property: for

$$c=ab-a-b,$$

exactly one of the two integers $n$ and $c-n$ belongs to $M$.

This is a Type C problem, because we must determine an extremal value, namely the largest integer outside $M$, and prove that no larger one exists.

The main difficulty is finding a canonical description of all integers relative to the semigroup generated by $a$ and $b$, and then using it to establish the symmetry between $n$ and $c-n$.

The expected answer is

$$c=ab-a-b.$$

The intuition is that residues modulo $a$ are represented uniquely by $0,b,\ldots,(a-1)b$, and the number $ab-a-b$ sits exactly at the boundary where every larger integer becomes representable.

Proof Architecture

Lemma 1. Every integer $n$ admits a unique representation

$$n=jb+qa, \qquad 0\le j\le a-1,$$

with $q\in\mathbb Z$; uniqueness follows because multiplication by $b$ permutes the residue classes modulo $a$.

Lemma 2. For an integer written as in Lemma 1, $n\in M$ if and only if $q\ge0$; any representation with $0\le j\le a-1$ is canonical, and a nonnegative representation forces $q\ge0$.

Lemma 3. Let

$$c=ab-a-b.$$

If

$$n=jb+qa, \qquad 0\le j\le a-1,$$

then

$$c-n=(a-1-j)b+(-1-q)a.$$

This is a direct computation.

Lemma 4. Exactly one of $n$ and $c-n$ belongs to $M$; by Lemma 2, membership is determined by the sign of $q$, while for $c-n$ it is determined by the sign of $-1-q$.

Lemma 5. The number $c$ does not belong to $M$; applying Lemma 4 to $n=c$ shows that $0\in M$ and $c\notin M$.

Lemma 6. Every integer larger than $c$ belongs to $M$; if $n>c$, then $c-n<0$, and negative integers cannot lie in $M$, so Lemma 4 forces $n\in M$.

The most delicate point is Lemma 2, where one must prove that a canonical representation with $q<0$ cannot be rewritten with nonnegative coefficients.

Solution

Let

$$M={ax+by:x,y\in\mathbb Z_{\ge0}},$$

where $a$ and $b$ are coprime positive integers.

Since $\gcd(a,b)=1$, the numbers

$$0,b,2b,\ldots,(a-1)b$$

represent all residue classes modulo $a$ exactly once. Hence for every integer $n$ there exists a unique pair $(j,q)$ such that

$$n=jb+qa, \qquad 0\le j\le a-1, \qquad q\in\mathbb Z.$$

We first characterize membership in $M$.

Suppose

$$n=jb+qa, \qquad 0\le j\le a-1.$$

If $q\ge0$, then

$$n=qa+jb,$$

and both coefficients are nonnegative, so $n\in M$.

Conversely, assume $n\in M$. Then

$$n=xa+yb$$

for some $x,y\ge0$. Since

$$n=jb+qa,$$

we obtain

$$(y-j)b=(q-x)a.$$

Because $\gcd(a,b)=1$, there exists an integer $t$ such that

$$y-j=ta, \qquad q-x=tb.$$

Hence

$$y=j+ta.$$

Since $0\le j\le a-1$ and $y\ge0$, the integer $t$ cannot be negative. Indeed, if $t\le-1$, then

$$y=j+ta\le(a-1)-a=-1,$$

contrary to $y\ge0$.

Therefore $t\ge0$, and

$$q=x+tb\ge0.$$

We have proved

$$n\in M \quad\Longleftrightarrow\quad q\ge0.$$

Now define

$$c=ab-a-b.$$

Let

$$n=jb+qa, \qquad 0\le j\le a-1.$$

Then

$$\begin{aligned} c-n &=(ab-a-b)-(jb+qa)\ &=(a-1-j)b+(-1-q)a. \end{aligned}$$

Since

$$0\le a-1-j\le a-1,$$

this is the canonical representation of $c-n$.

Applying the criterion already proved, we obtain

$$n\in M \quad\Longleftrightarrow\quad q\ge0,$$

and

$$c-n\in M \quad\Longleftrightarrow\quad -1-q\ge0.$$

The inequalities

$$q\ge0, \qquad -1-q\ge0$$

cannot hold simultaneously, and one of them must hold because $q$ is an integer.

Hence exactly one of the numbers $n$ and $c-n$ belongs to $M$.

This proves part 2.

To determine the largest integer outside $M$, substitute $n=c$ into the statement just proved. Since

$$c-c=0\in M,$$

the number $c$ itself does not belong to $M$.

Now let $n>c$. Then

$$c-n<0.$$

Every element of $M$ is nonnegative, so $c-n\notin M$. By the property proved above, exactly one of $n$ and $c-n$ belongs to $M$, therefore $n\in M$.

Thus every integer greater than $c$ lies in $M$, while $c$ does not. Consequently $c$ is the largest integer not belonging to $M$.

Therefore

$$\boxed{c=ab-a-b}.$$

Equality is attained by the number $ab-a-b$, and every integer larger than it belongs to $M$.

Verification of Key Steps

The first delicate step is the characterization of $M$ by the sign of $q$.

Assume

$$n=jb+qa, \qquad 0\le j\le a-1,$$

and also

$$n=xa+yb, \qquad x,y\ge0.$$

From

$$(y-j)b=(q-x)a$$

we deduce

$$y-j=ta.$$

If one forgets to use $0\le j\le a-1$, one might incorrectly allow negative $t$. The bound on $j$ gives

$$y=j+ta<0$$

whenever $t\le-1$, contradicting $y\ge0$. This forces $t\ge0$ and hence $q=x+tb\ge0$.

The second delicate step is verifying that the expression for $c-n$ is canonical. We obtain

$$c-n=(a-1-j)b+(-1-q)a.$$

Since

$$0\le j\le a-1,$$

we have

$$0\le a-1-j\le a-1.$$

Without checking this range, one could not apply the membership criterion to $c-n$.

The third delicate step is the exclusivity argument. For an integer $q$, either $q\ge0$ or $q\le-1$. In the first case,

$$-1-q<0.$$

In the second case,

$$-1-q\ge0.$$

Thus exactly one of the two coefficients governing membership is nonnegative. There is no exceptional value of $q$ where both conditions fail or both hold.

Alternative Approaches

A classical geometric approach considers lattice points $(x,y)$ with $x,y\ge0$ and the lines

$$ax+by=n.$$

For each residue class modulo $a$, one identifies the smallest representable number and counts the nonrepresentable integers below $ab$. The boundary point corresponding to $(b-1,a-1)$ leads to the value $ab-a-b$. The symmetry arises from reflecting lattice points inside the rectangle

$$0\le x\le b-1,\qquad 0\le y\le a-1.$$

Another approach works entirely modulo $a$. For each residue class choose the least element of $M$ in that class, namely

$$0,b,2b,\ldots,(a-1)b.$$

An integer in the residue class of $jb$ is representable precisely when it is at least $jb$. This immediately yields the largest nonrepresentable integer as

$$\max_{0\le j\le a-1}\bigl(jb-a\bigr)=ab-a-b.$$

The canonical-representation method used in the main proof is preferable because it simultaneously yields the extremal value and the symmetry statement in a single calculation.