Polynomials over a finite field

Oh well, here we go again. Back to Maths posts.

Tragedy struck since the last time we saw, my dear viewers. Oxford rejected me, but there's no time to waste, since the world of Maths is waiting. While going through National Olympiad shortlists, I found the following problem in the shortlist for 2013, randomly sitting at the middle of a page, waiting to be solved. It's a problem about polynomials, so I was surprised when I saw that I could solve it, because I'm not normally great at solving polynomial problems.

Let \(p>1\) be a prime, \((K, +, *)\) be a field with \(p^2\) elements and \(L=[0, 1, ... 1+1+...+1]\), with the last sum having \(p-1\) elements. Prove that for every \(x∊K-L\), there exists \(a,b∊L\) so that \(x^{2013}+ax+b=0\).

Solution:

I'm not sure if there are more ways of solving this particular problem, so for this you really need to have the idea.

Let us presume that there is an element \(x∊K-L\) such that \(x^{2013}+ax+b\) is always different than 0. The first observation is that have \(p^2-p\) elements in \(K-L\). Now, let \(A={(F(X)|F(X)=X^{2013}+aX+b}\). This set has cardinal \(p^2\). Since the cardinal of A is bigger than the cardinal of \(K-L\), we have that at least two polynomials from A have the same value in \(x\).

Let \(f_1\) and \(f_2\) be the associated polynomial functions of the polynomials we found. Thus, \(f_1(x)=f_2(x)\), so \(x^{2013}+a_1 x+ b_1=x^{2013}+a_2 x+ b_2\), so \((a_1 - a_2) x + (b_1 - b_2)=0\). Thus, \(x = (b_2 - b_1)(a_1-a_2)^{-1}∊L\), because \(a_1, a_2, b_1, b_2\) all belong to L and, because p is prime, L is closed under any operation. This contradicts the way we chose x, and thus the problem is solved.

The problem wasn't necessarily hard, but the idea was pretty important. This trick of finding two polynomial functions which have the same value in a point is widely used, though this is the first time I see it used in an abstract algebra problem. Tune in next time, when I might talk about inequalities and analysis, or something else, completely random.

Cris.