Vietnamese Mathematical Olympiad

We first state a well-known lemma
Lemma. (Sylvester's theorem) For two positive integers $a$ and $b$ such that $\gcd(a, b) = 1$, the largest integer that could not be written in the form $a x + b y$ where $x$ and $y$ are non-negative integers is $N_0 = ab - a - b$.

a) Let $a$ be the satisfying value. A natural number $n$ is called 'nice' if there exists $x, y, z \in \mathbb{N}$ such that
$$a^2x + 6a y + 36z = n.$$
By choosing $n = 301$, we have $a^2x \equiv 1 \pmod{6}$ then $\gcd(a, 6) = 1$, which implies $\gcd(a, 36) = 1$. Moreover, by applying the Sylvester's theorem for $a$ and $36$, the largest number could not be written in the form $a x_1 + 36 y_1$ is
$$36a - a - 36 = 35a - 36.$$
However,
$$n = a^2x + 6a y + 36z = a(ax + 6y) + 36z = a x_1 + 36 y_1,$$
hence $n \ge 35a - 35$ which means $250 \ge 35a - 35$ or $a < 9$. Since $\gcd(a, 6) = 1$, we conclude $a \in \{1, 5, 7\}$.

* For $a = 7$, the equation becomes $n = 49x + 42y + 36z$ and by putting $n = 251$, we get
$$251 = 49x + 42y + 36z \equiv z \pmod{7} \text{ hence } z \equiv 6 \pmod{7}.$$
This means $z \ge 6$. On the other hand, $z \le 251/36 < 13$ then $z = 6$. The equation becomes $7x + 6y = 5$, which has no natural solution then $a = 7$ is not satisfied.

* For $a = 1$, the equation always has a solution $(x, y, z) = (n, 0, 0)$.

* For $a = 5$, we have to show that for $n \ge 250$, there exists $(x, y, z) \in \mathbb{N}^3$ such that
$$25x + 30y + 36z = n.$$
Putting $n = 5k + r, z = r$ where $r < 5$ and $k \ge 50$, the equation becomes
$$25x + 30y = n - 36r = 5k - 35r \Leftrightarrow 5x + 6y = k - 7r.$$
However, $k-7r \ge 50-28 = 22 > 30-5-6$ then by Sylvester's theorem, the equation always has natural solution.

b) We prove a general result: Let $a, b$ be two coprime positive integers. Then
$$N = a^2b + ab^2 - a^2 - b^2 - ab + 1$$
is the smallest positive integer which the equation $a^2x + ab y + b^2z = m$ has natural solution for all $m \ge N$.

* In case $m \ge N$, choosing $z = m b^{-2}$ (mod $a$) ($0 \le z < a$) and we need to prove that there exists $x, y \in \mathbb{N}$ such that the equation
$$ax + by = \frac{m - b^2 z}{a}$$
has natural solution. Note that
$$\frac{m - b^2 z}{a} \ge \frac{N - b^2(a - 1)}{a} > \frac{a^2 b - a^2 - ab}{a} = ab - a - b$$
then the equation always has a natural solution by Sylvester's theorem.

* If $m < N$, let $m = a^2b + ab^2 - a^2 - b^2 - ab$ and assume that there exists a triple $(x, y, z) \in \mathbb{N}^3$ such that
$$a^2x + ab y + b^2z = m$$
hence $a^2x \equiv -a^2 \pmod{b}$, $b^2z \equiv -b^2 \pmod{a}$ which is equivalent to
$$x \equiv -1 \pmod{b}, z \equiv -1 \pmod{a}.$$
Then $x \ge b - 1, z \ge a - 1$ which leads to
$$y \le \frac{m - a^2(b - 1) - b^2(a - 1)}{ab} = -1.$$
That is a contradiction since $y \ge 0$.

Applying this result, we conclude that the greatest value of $n$ is $5a^2 + 30a - 36$. $\square$