Tessellate S.T.E.M.S - Mathematics - School - Set 3 - Problem 1

Number Theory Level 3

$A$ and $B$ play a game. First, $A$ picks an integer $a_1$ . Then $B$ picks an integer $a_2$ . Finally, $A$ picks an integer $a_3$ .

$B$ wins if the polynomial $\displaystyle x^3 + a_2x^2 + a_1x + a_3$ has a root modulo $3$ , $A$ wins otherwise.

Which of the following numbers can be $A$ 's choice for $a_1$ if he wishes to have a winning strategy?

This problem is a part of Tessellate S.T.E.M.S.

43 42 40 41

1 solution

Leonel Castillo
Jan 8, 2018

First, notice that the given polynomial reduces to $a_2 x^2 + (a_1 + 1)x + a_3$ . Looking at this polynomial one may be immediately tempted to try $a_1 = 2$ so that the polynomial then becomes $a_2 x^2 + a_3$ . I will show that no matter what B picks for $a_2$ , there is a suitable $a_3$ . First, if $a_2 = 0$ then choose $a_3 = 1$ . If $a_2 = 1$ then pick $a_3 = -2$ because there is no solution for $x^2 \equiv 2 \mod 3$ and if $a_2 = 2$ then pick $a_3 = 2$ because then $2x^2 + 2 \equiv 0 \iff x^2 + 1 \equiv 0 \iff x^2 \equiv 2 \mod 3$ which is impossible, as mentioned before.

So choosing $a_1 = 2$ gives us a perfect strategy. Now simply notice that $41 = 3 \times 13 + 2$ .

Will you explain it in an easier way

Naaz Hussain - 3 years, 4 months ago

Well, can you explain how the given expression becomes a2x^2 + (a1+1)x + a3 And by the way can anyone tell what does the question mean by root modulo 3

Anu Radha - 3 years, 4 months ago

By Fermat's little theorem x^3 = x modulo 3 so I just applied that. Also by root modulo 3 that just means you should consider the polynomial as a polynomial over the integers modulo 3 and then a root modulo 3 is an integer modulo 3 makes the polynomial evaluate to 0 modulo 3. All of this has to do with congruences.

Leonel Castillo - 3 years, 4 months ago

Tessellate S.T.E.M.S - Mathematics - School - Set 3 - Problem 1

1 solution

0 pending reports