Belarusian Mathematical Olympiad

1. It is straightforward to verify the following
Lemma. Let $x^2 + bx + c$ be a trinomial with integer coefficients which is not divisible by $3$ for any integer $x$. Then this trinomial is congruent modulo $3$ to one of the next three trinomials: $x^2 + 1$, $x^2 + x - 1$ and $x^2 - x - 1$.
Denote $x^2 + 1 = p_1(x)$, $x^2 + x - 1 = p_2(x)$ and $x^2 - x - 1 = p_3(x)$. The straightforward verification shows that $x^6 + x^4 + x^2 + 1 \equiv p_1(x) \cdot p_2(x) \cdot p_3(x) \pmod{3}$. Therefore, we can change the polynomial $x^6 + x^4 + x^2 + 1$ in the condition by the polynomial $p_1(x)p_2(x)p_3(x)$.

Let $p(x) = ax^2 + bx + c$. We distinguish two cases.

Case 1: $p(a) = 0$. Then there exists $a_0$ such that $aa_0 \equiv 1 \pmod{3}$. Applying the lemma to $a_0p(x)$ we get $a_0p(x) \equiv p_i(x) \pmod{3}$, $1 \le i \le 3$. That is, there exists $h_0(x)$ such that $a_0p(x) = p_i(x) - 3h_0(x)$. Multiply this equality by $p_{i+1}(x)p_{i+2}(x)$ (where $3+1=2+2=1$ and $3+2=2$) to obtain $a_0p(x)p_{i+1}(x)p_{i+2}(x) = p_1(x)p_2(x)p_3(x) - 3h_0(x)p_{i+1}(x)p_{i+2}(x)$. It remains to set $f(x) = a_0p_{i+1}(x)p_{i+2}(x)$ and $h(x) = h_0(x)p_{i+1}(x)p_{i+2}(x)$.

Case 2: $p|a$. In this case $bx + c$ is not divisible by $3$ for all integer $x$, whence $3|b$ and $3|c$. Thus there exists integer $c_0$ such that $cc_0 \equiv 1 \pmod{3}$. So we can set $h(x) \equiv 0$ and $f(x) = c_0(x^6 + x^4 + x^2 + 1)$.