Problem 1243

We need to prove that if $a$ is a natural number greater than $1$, then the number

is divisible by $504 = 7 \cdot 8 \cdot 9$. Since the numbers $7$, $8$, and $9$ are pairwise coprime, the task reduces to proving the divisibility of $N$ by each of these numbers.
a) The number $a$ can be represented in the form $a = 7k + r$, where $k$ is a natural number, and $r$ is one of the numbers $0$, $1$, $2$, $3$, $4$, $5$, $6$. Then $a^3 = 7^3k^3 + 3 \cdot 7^2k^2r + 3 \cdot 7kr^2 + r^3$, so when divided by $7$, the number $a^3$ gives the same remainder as $r^3$. But $r^3$ is one of the numbers $0$, $1$, $8$, $27$, $64$, $125$, $216$, so the remainder of $a^3$ when divided by $7$ is one of the numbers $0$, $1$, $6$, which means that one of the numbers $a^3$, $a^3 - 1$, $a^3 + 1$ is divisible by $7$.
b) To establish the divisibility of the number $N$ by $8$, it suffices to note that if $a$ is an even number, then $a^3$ is divisible by $8$, and if $a$ is odd, then $a^3 - 1$ and $a^3 + 1$ are two consecutive even numbers, one of which is divisible by $4$, and their product by $8$.
c) The number $a$ can be represented in the form $a = 3l + s$, where $l$ is a natural number, and $s$ is one of the numbers $0$, $1$, $2$. Then $a^3 = 3^3l^3 + 3 \cdot 3l^2s + 3 \cdot 3l \cdot s^2 + s^3$, from which we see that $a^3$ gives a remainder of $s^3$ when divided by $9$, i.e., $0$, $1$, or $8$. Therefore, one of the numbers $a^3$, $a^3 - 1$, or $a^3 + 1$ is divisible by $9$.
Note 1. It is easy to observe that in the statement of the theorem, we can speak more generally about integers instead of natural numbers.
Note 2. Using simple facts from number theory, the arguments presented above in points a) and c) can be replaced with simpler ones. According to Fermat's Little Theorem (see Seventh Mathematical Olympiad, Warsaw 1957, problem no. 2), if an integer $a$ is not divisible by $7$, then the congruence

holds, from which it follows that

Thus, if $a$ is any integer, one of the numbers $a^3$, $a^3 - 1$, $a^3 + 1$ is divisible by $7$.
When it comes to divisibility by $9$, which is not a prime number, a more general theorem than Fermat's must be applied, namely Euler's Theorem (the famous Swiss mathematician, 1707-1783). Let $m$ be a natural number, and let $\varphi(m)$ denote the number of natural numbers not greater than $m$ and coprime with $m$. For example, $\varphi(1) = \varphi(2) = 1$, $\varphi(3) = \varphi(4) = 2$, $\varphi(5) = 4$, $\varphi(6) = 2$, $\varphi(7) = 6$, $\varphi(8) = 4$, $\varphi(9) = 6$, etc.
Euler's Theorem states: If the integers $a$ and $m > 1$ are coprime, then

For example, if $m = 9$, we get the theorem: if the integer $a$ is not divisible by $3$, then

from which - as above - it follows that for any integer $a$, one of the numbers $a^3$, $a^3 - 1$, $a^3 + 1$ is divisible by $9$.
A proof of Euler's Theorem can be conducted as follows. Let $r_1, r_2, \ldots, r_\varphi$, where $\varphi = \varphi(m)$, be the increasing sequence of all natural numbers not greater than $m$ and coprime with $m$. Then each of the numbers $ar_1, ar_2, \ldots, ar_\varphi$ is also coprime with $m$; let $\rho_1, \rho_2, \ldots, \rho_\varphi$ denote the remainders of these numbers when divided by $m$, so

Each of the numbers $\rho_i$ is coprime with $m$, because according to (1) $\alpha r_i - \varphi_i$ is divisible by $m$, and $\alpha r_i$ is coprime with $m$. Moreover, the numbers $\rho_i$ are all different, because from the equality $\rho_i = \rho_k$ it would follow that $\alpha r_i \equiv \alpha r_k \pmod m$, and thus $r_i \equiv r_k \pmod m$, i.e., $r_i \equiv r_k$, contrary to the definition of the numbers $r_i$. Therefore, the numbers $\rho_1, \rho_2, \ldots, \rho_\varphi$ differ from the numbers $r_1, r_2, \ldots, r_\varphi$ at most in order, and the equality

holds.
Multiplying the congruences (1) side by side, we get

Since each of the numbers $r_i$ is coprime with $m$, the same applies to the product of these numbers, so from (2) and (3) it follows that

which was to be proved.
Note that if $m$ is a prime number, then $\varphi(m) = m - 1$; in this case, Euler's Theorem gives Fermat's Little Theorem.