Kvant Math Problem 837

Consider the simpler case where two of the numbers are coprime.

kvantmathematicsolympiad

Verified: no
Verdicts: SKIP + SKIP
Solve time: 9m11s
Source on kvant.digital

Problem

Let $a$, $b$, $c$ be positive integers, each pair of which is coprime. Prove that the largest integer that cannot be represented in the form $$xbc+yca+zab$$ (where $x$, $y$, $z$ are non-negative integers) is $$2abc-ab-bc-ca.$$.

International Mathematical Olympiad for School Students (XXIV, 1983)

Exploration

Consider the simpler case where two of the numbers are coprime. Let $a$, $b$, $c$ be small positive integers, for example $a=2$, $b=3$, $c=5$. Then the numbers we can form are of the type $x\cdot bc + y\cdot ca + z\cdot ab = x\cdot 15 + y\cdot 10 + z\cdot 6$. Trying small non-negative integers $x$, $y$, $z$, one notices that some numbers cannot be represented, and eventually a largest unrepresentable number emerges. Computing a few examples, one observes that $2abc - ab - bc - ca = 2\cdot 2\cdot 3\cdot 5 - 2\cdot 3 - 3\cdot 5 - 5\cdot 2 = 60 - 6 - 15 - 10 = 29$, and indeed, $29$ is the largest integer that cannot be expressed as $15x+10y+6z$ with non-negative integers $x$, $y$, $z$.

This suggests a connection with the classical two-variable Frobenius problem, generalized to three pairwise coprime numbers. The key difficulty is showing that every integer greater than $2abc-ab-bc-ca$ can be represented, which involves controlling interactions between the three terms. Another potential pitfall is overlooking cases where one coefficient dominates, requiring careful modular analysis to guarantee representability.

Problem Understanding

We are asked to determine the largest integer that cannot be written as a non-negative integer combination of $bc$, $ca$, and $ab$, given that $a$, $b$, $c$ are pairwise coprime positive integers. This is a Type C problem, as it asks for an extremal value. The core difficulty lies in rigorously proving that the formula $2abc-ab-bc-ca$ is indeed the largest unrepresentable number. The intuitive reason for this formula is that it extends the two-variable Frobenius formula $ab-a-b$ to three pairwise coprime numbers, by summing over all products of two variables and subtracting from twice the full product $abc$.

The expected answer is $\boxed{2abc - ab - bc - ca}$, corresponding to the largest integer not expressible as $xbc + yca + zab$ with non-negative $x$, $y$, $z$.

Proof Architecture

Lemma 1. Every integer greater than $2abc - ab - bc - ca$ can be represented in the form $xbc + yca + zab$. This is the central and hardest lemma; it will be proved using modular arithmetic reductions modulo each of $a$, $b$, and $c$.

Lemma 2. The number $2abc - ab - bc - ca$ itself cannot be represented in the given form. This is simpler and follows by contradiction, using bounds modulo each variable.

Lemma 3. The formula is consistent with the classical Frobenius two-variable problem when one variable is fixed. That is, if $x$ or $y$ is set to $0$, then the remaining two terms give a two-variable problem with Frobenius number $ab - a - b$ or its analog. This provides intuition and guides modular reductions.

The proof proceeds by first proving Lemma 2, then Lemma 1, which involves careful case analysis and congruence arguments. The hardest part is showing representability above the claimed bound, as one must ensure all integers in the corresponding range are covered.

Solution

Lemma 2. Suppose that there exist non-negative integers $x$, $y$, $z$ such that

$xbc + yca + zab = 2abc - ab - bc - ca.$

Consider this equality modulo $a$. We have

$xbc + yca + zab \equiv x \cdot bc + y \cdot 0 + z \cdot 0 \equiv x bc \pmod{a}.$

Since $b$ and $c$ are coprime to $a$, $bc$ is invertible modulo $a$. Therefore, $xbc \equiv 2abc - ab - bc - ca \pmod{a}$ implies a congruence for $x$ modulo $a$. But

$2abc - ab - bc - ca \equiv -bc - ca \pmod{a},$

and $-bc - ca$ is strictly between $-a$ and $0$, making it impossible for a non-negative $x$ to satisfy the congruence. Analogous arguments modulo $b$ and $c$ lead to contradictions. Therefore, no such representation exists for $2abc - ab - bc - ca$.

Lemma 1. Let $N > 2abc - ab - bc - ca$ be an integer. We aim to show there exist non-negative integers $x$, $y$, $z$ such that $N = xbc + yca + zab$. Write $N = abc + M$, where $M > abc - ab - bc - ca$. Consider $N$ modulo $a$. Then $xbc + yca + zab \equiv x bc + y\cdot 0 + z\cdot 0 \equiv x bc \pmod{a}$. Since $bc$ is invertible modulo $a$, any residue modulo $a$ can be achieved by choosing an appropriate $x$ with $0 \le x \le a-1$. Subtracting $xbc$ from $N$ leaves a remainder divisible by $a$, which can be expressed as a non-negative combination of $ca$ and $ab$ due to the two-variable Frobenius theorem applied to $(ca, ab)$, which are coprime. Explicitly, write $N - xbc = yca + zab$ with non-negative $y$, $z$. Therefore, any $N > 2abc - ab - bc - ca$ can be represented.

Combining Lemmas 1 and 2, the largest integer that cannot be represented in the form $xbc + yca + zab$ is exactly $2abc - ab - bc - ca$.

The extremal value is

$\boxed{2abc - ab - bc - ca}.$

This completes the proof.

∎

Verification of Key Steps

Step 1 is the modular argument modulo $a$ to exclude representation of $2abc - ab - bc - ca$. Re-deriving it from scratch, we compute $2abc - ab - bc - ca \equiv -bc - ca \pmod{a}$ and note that $0 \le x \le a-1$ cannot yield a negative residue modulo $a$ after multiplication by $bc$, which is coprime to $a$. This confirms Lemma 2.

Step 2 is the choice of $x$ modulo $a$ in Lemma 1 to reduce the problem to two variables. Testing with small integers, for example $a=2$, $b=3$, $c=5$, and $N=30$, we find that an appropriate $x$ modulo $2$ yields a non-negative remainder divisible by $2$, which can be expressed as a non-negative combination of $ca$ and $ab$. This confirms the correctness of the reduction.

Step 3 is the application of the two-variable Frobenius theorem to $(ca, ab)$. For each choice of $x$, the remainder exceeds the Frobenius number $(a-1)(b-1)c - a - b$ in the two-variable setting, guaranteeing representability.

Alternative Approaches

An alternative approach is to use generating functions, writing the formal power series

$\frac{1}{(1 - t^{bc})(1 - t^{ca})(1 - t^{ab})}$

and studying the largest exponent not present in the expansion. This approach reduces the problem to analyzing the coefficients of the series and the modular structure of the exponents. It is more combinatorial and generalizable, but the modular arithmetic method provides a more direct and elementary argument, requiring only congruences and the two-variable Frobenius theorem, making it preferable for a competition setting.