Maths Olympiad Prep

Library / /25 of 52

Number theory Difficulty 5.9 AIME, harder Prove it Belarus

Given a quadratic trinomial p(x)p(x) with integer coefficients such that p(x)p(x) is not divisible by 33 for all integers xx.
Prove that there exist polynomials f(x)f(x) and h(x)h(x) with integer coefficients such that
p(x)f(x)+3h(x)=x6+x4+x2+1. p(x) \cdot f(x) + 3h(x) = x^6 + x^4 + x^2 + 1.

Solution

1. It is straightforward to verify the following
Lemma. Let x2+bx+cx^2 + bx + c be a trinomial with integer coefficients which is not divisible by 33 for any integer xx. Then this trinomial is congruent modulo 33 to one of the next three trinomials: x2+1x^2 + 1, x2+x1x^2 + x - 1 and x2x1x^2 - x - 1.
Denote x2+1=p1(x)x^2 + 1 = p_1(x), x2+x1=p2(x)x^2 + x - 1 = p_2(x) and x2x1=p3(x)x^2 - x - 1 = p_3(x). The straightforward verification shows that x6+x4+x2+1p1(x)p2(x)p3(x)(mod3)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 x6+x4+x2+1x^6 + x^4 + x^2 + 1 in the condition by the polynomial p1(x)p2(x)p3(x)p_1(x)p_2(x)p_3(x).

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

Case 1: p(a)=0p(a) = 0. Then there exists a0a_0 such that aa01(mod3)aa_0 \equiv 1 \pmod{3}. Applying the lemma to a0p(x)a_0p(x) we get a0p(x)pi(x)(mod3)a_0p(x) \equiv p_i(x) \pmod{3}, 1i31 \le i \le 3. That is, there exists h0(x)h_0(x) such that a0p(x)=pi(x)3h0(x)a_0p(x) = p_i(x) - 3h_0(x). Multiply this equality by pi+1(x)pi+2(x)p_{i+1}(x)p_{i+2}(x) (where 3+1=2+2=13+1=2+2=1 and 3+2=23+2=2) to obtain a0p(x)pi+1(x)pi+2(x)=p1(x)p2(x)p3(x)3h0(x)pi+1(x)pi+2(x)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)=a0pi+1(x)pi+2(x)f(x) = a_0p_{i+1}(x)p_{i+2}(x) and h(x)=h0(x)pi+1(x)pi+2(x)h(x) = h_0(x)p_{i+1}(x)p_{i+2}(x).

Case 2: pap|a. In this case bx+cbx + c is not divisible by 33 for all integer xx, whence 3b3|b and 3c3|c. Thus there exists integer c0c_0 such that cc01(mod3)cc_0 \equiv 1 \pmod{3}. So we can set h(x)0h(x) \equiv 0 and f(x)=c0(x6+x4+x2+1)f(x) = c_0(x^6 + x^4 + x^2 + 1).

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.