Bulgarian Winter Tournament

Lemma. Let $p$ be a prime number and $a$, $b$, $c\in \mathbb{Z}/p\mathbb{Z}$. Then there exist $x$, $y$, $z\in \mathbb{Z}$ such that $|x|$, $|y|$, $|z|<\sqrt[3]{p}$, $(x,y,z)\ne (0,0,0)$ and $ax+by+cz\equiv 0(\mathrm{mod}p)$.

Proof. Consider the set $M:=\{(x,y,z):x,y,z\in \{0,1,\dots ,\lfloor \sqrt[3]{p}\rfloor \}\}$. We have that $|M|>p$, i.e. in $M$ there are two distinct elements $(x_1,y_1,z_1)$ and $(x_2,y_2,z_2)$, for which $a{x}_1+b{y}_1+c{z}_1\equiv a{x}_2+b{y}_2+c{z}_2(\mathrm{mod}p)$. Thus $(x_1-x_2,y_1-y_2,z_1-z_2)$ satisfies the conditions of the lemma.

Now let $p\equiv 2(\mathrm{mod}3)$. Then the comparison $x^3\equiv 2(\mathrm{mod}p)$ has a solution $a$, since the function $x\mapsto x^3$ is injective in $\mathbb{Z}/p\mathbb{Z}$, hence it is surjective. One way to verify this is to see that $x^3\equiv 1(\mathrm{mod}p)$ has only $1$ for a solution, since $(3,p-1)=1$ and hence the exponent of $x$ (mod $p$) is $1$.

From the lemma, there exist $x$, $y$, $z$ with $|x|$, $|y|$, $|z|<\sqrt[3]{p}$, for which $x+ay+a^{2}z\equiv 0(\mathrm{mod}p)$. From here we get that $x^3+a^3{y}^3+a^6{z}^3-3a^{3}xyz\equiv 0(\mathrm{mod}p)$. The latter is equivalent to $x^3+2y^3+4z^3-6xyz\equiv 0(\mathrm{mod}p)$.

On the other hand $|x|$, $|y|$, $|z|<\sqrt[3]{p}$ gives $|x^3+2y^3+4z^3-6xyz|<13p$. Also notice that if $x^3+2y^3+4z^3-6xyz<0$, then the triple $(-x,-y,-z)$ will give a natural number divisible by $p$.

It remains to note that $x^3+2y^3+4z^3-6xyz\ne 0$. Indeed, if $x^3+2y^3+4z^3-6xyz=0$, then we have $(x+\sqrt[3]{2}y+\sqrt[3]{4}z)((x-\sqrt[3]{2}y{)}^2+(x-\sqrt[3]{4}z{)}^2+(\sqrt[3]{2}y-\sqrt[3]{4}z{)}^2)=0$, i.e. $x=\sqrt[3]{2}y=\sqrt[3]{4}z$ or $x+y\sqrt[3]{2}+z\sqrt[3]{4}=0$, whose only integer solutions are $(x,y,z)=(0,0,0)$ (the first follows because $\sqrt[3]{2}$ is irrational, and the second follows from the fact that $x^3-2$ is the minimal polynomial of $\sqrt[3]{2}$ over the rational numbers). $\square$