This note presents a simple, classical number‑theory result: for natural numbers \(b,c,m,n\in\mathbb N\) with \(\gcd(b,c)=1\), the quantity \(bc-b-c\) is the largest integer that cannot be written as \(mb+nc\).1 I’ll first prove the statement and then show a short application that turns an Olympiad‑style problem into a few lines.

By the “conductor” of two natural numbers we mean the product of the numbers minus their sum. In symbols,

\[\operatorname{Conductor}(x, y) = xy - x - y\]

The theorem below turns the original task into a short argument, and the same idea is useful in other settings as well.

Main Theorem

Theorem (Conductor of Two Naturals):

Let \(b,c\in\mathbb{N}\) with \(\gcd(b,c)=1\). The conductor \(bc - b - c\) is the largest number that cannot be written as \(mb + nc\) for non‑negative integers \(m,n\).

Proof:

Without loss of generality assume \(b < c\) and \(\gcd(b,c)=1\).

\[0,\ c,\ 2c,\ 3c,\ 4c,\ \ldots,\ (b-2)c,\ (b-1)c\]

is an exhaustive set of residues modulo \(b\).[^residues-mod-b]

Take any integer \(r\) with

\begin{equation} r > (b-1)c - b \label{eq:r-bound} \end{equation}

Then there exists \(n\in\{0,\ldots,b-1\}\) such that

\begin{equation} r \equiv nc \pmod b. \label{eq:r-equiv} \end{equation}

Setting \(m := (r-nc)/b \ge 0\) gives \(r = mb+nc\). Hence any integer strictly larger than \(bc-b-c\) can be written as \(mb+nc\).

It remains to show that \(bc-b-c\) itself is not representable. Assume, for a contradiction, that

\begin{equation} bc-b-c = mb+nc. \label{eq:contradiction} \end{equation}

Reducing (\ref{eq:contradiction}) modulo \(b\) and using \(\gcd(b,c)=1\) yields \(nc \equiv -c\pmod b\Rightarrow n\equiv -1\pmod b\), so \(n\ge b-1\). Therefore

\begin{equation} mb+nc \ge nc \ge (b-1)\cdot c > bc-b-c, \label{eq:final-contradiction} \end{equation}

which is a contradiction.

Usage

We will now see a problem where using this theorem makes it significantly easier. This problem is from The International Mathematical Olympiad (IMO) 1983 Day 1 Problem 3 2.

Problem

Let \(a,b\) and \(c\) be positive integers, no two of which have a common divisor greater than \(1\).3 Show that \(2abc-ab-bc-ca\) is the largest integer which cannot be expressed in the form \(xbc+yca+zab\), where \(x,y,z\) are non-negative integers.

Using the theorem, we use the same starting argument:

\[0,\ bc,\ 2bc,\ 3bc,\ 4bc,\ \ldots,\ (a-2)bc,\ (a-1)bc\]

is an exhaustive set of residues modulo \(a\).

Given

\begin{equation} N > 2abc - ab - bc - ca \label{eq:N-bound} \end{equation}

we may take

\begin{equation} xbc \equiv N \pmod a,\quad 0 \leq x < a \label{eq:x-equiv} \end{equation}

Then

\[\begin{equation} \begin{aligned} N - xbc &> 2abc - ab - bc - ca - (a-1)bc \\ &= abc - ab - ca \\ &= a\big( bc - b - c \big) \end{aligned} \label{eq:N-minus-xbc} \end{equation}\]

So

\begin{equation} N - xbc = ka \quad \text{with} \quad k > bc - b - c \label{eq:k-definition} \end{equation}

Hence we can find non-negative \(y, z\) so that

\begin{equation} k = zb + yc \label{eq:k-form} \end{equation}

Therefore

\begin{equation} N = xbc + yca + zab \label{eq:N-final} \end{equation}

Finally, we show that for \(N = 2abc - ab - bc - ca\) we cannot find non-negative \(x, y, z\) such that \(N = xbc + yca + zab\). Indeed,

\begin{equation} N \equiv -bc \pmod a \label{eq:N-mod} \end{equation}

so we must have \(x \equiv -1 \pmod a\) and hence \(x \geq a-1\). Similarly, \(y \geq b-1\) and \(z \geq c-1\).4 Thus

\begin{equation} xbc + yca + zab \geq 3abc - ab - bc - ca > N \label{eq:usage-contradiction} \end{equation}

which is a contradiction.

Citation

Please cite this work as:

Rishit Dagli. "What Is the Largest Integer Not of the Form mb+nc?". Rishit Dagli's Blog (November 2021). https://rishit-dagli.github.io/2021/11/04/conductor-of-two-naturals.html

Or use the BibTex citation:

@article{ dagli2021what,
  title = { What Is the Largest Integer Not of the Form mb+nc? },
  author = { Rishit Dagli },
  journal = {rishit-dagli.github.io},
  year = { 2021 },
  month = { November },
  url = "https://rishit-dagli.github.io/2021/11/04/conductor-of-two-naturals.html"
}

References

  1. We interpret “written as \(mb+nc\)” with \(m,n\in\mathbb{Z}_{\ge 0}\) (zero allowed). The coprimality condition \(\gcd(b,c)=1\) is essential: if \(d=\gcd(b,c)>1\), only multiples of \(d\) are representable as \(mb+nc\), so there is no finite “largest” non‑representable integer. This is the classical two‑variable case of the Frobenius coin problem, whose Frobenius number equals \(bc-b-c\). ↩

  2. International Mathematical Olympiad (IMO). The international mathematical olympiad (imo) 1983 problems, 1983. URL: https://www.imo-official.org/year_info.aspx?year=1983. ↩

  3. “No two have a common divisor greater than 1” means \(\gcd(a,b)=\gcd(b,c)=\gcd(c,a)=1\). This ensures that \(bc\) is invertible modulo \(a\), \(ca\) is invertible modulo \(b\), and \(ab\) is invertible modulo \(c\), which is used in the congruence arguments below. ↩

  4. From \(N\equiv -bc\pmod a\) and \(\gcd(a,bc)=1\) we infer \(xbc\equiv N\pmod a\Rightarrow x\equiv -1\pmod a\), giving \(x\ge a-1\). Reducing the same identity modulo \(b\) and \(c\) yields \(y\equiv -1\pmod b\) and \(z\equiv -1\pmod c\), hence \(y\ge b-1\) and \(z\ge c-1\). ↩