IMC 2000 · Day 2 · P7

We start with the following lemma: If $a$ and $b$ be coprime positive integers then every sufficiently large positive integer $m$ can be expressed in the form $ax + by$ with $x, y$ non-negative integers.

Proof of the lemma. The numbers $0, a, 2a, \dots, (b-1)a$ give a complete residue system modulo $b$. Consequently, for any $m$ there exists a $0 \le x \le b-1$ so that $ax \equiv m \pmod{b}$. If $m \ge (b-1)a$, then $y = (m - ax)/b$, for which $x + by = m$, is a non-negative integer, too.

Now observe that any dissection of a cube into $n$ smaller cubes may be refined to give a dissection into $n + (a^d - 1)$ cubes, for any $a \ge 1$. This refinement is achieved by picking an arbitrary cube in the dissection, and cutting it into $a^d$ smaller cubes. To prove the required result, then, it suffices to exhibit two relatively prime integers of form $a^d - 1$. In the 2-dimensional case, $a_1 = 2$ and $a_2 = 3$ give the coprime numbers $2^2 - 1 = 3$ and $3^2 - 1 = 8$. In the general case, two such integers are $2^d - 1$ and $(2^d - 1)^d - 1$, as is easy to check.