# Polynomial $P$ over a finite field $F_{q}$

I've just started with the theory of finite fields and I am stuck in an exercise, which must be not so difficult... Can anybody, please, give me a hint what can I do for to solve it?

Given is a finite field $F_{q}$ with $q$ elements, not necesserily prime and a function $f:F_{q}\rightarrow F_{q}$.
Prove that there exists a polynomial $P\in F_{q}[x]$, such that $P(x)=f(x)$ for every $x\in F_{q}$.

I would be glad, if someone could help me. Thank you in advance!

• If $F_q$ is a finite field, with $q$ elements, then $q$ must be prime, no? – Robert Lewis Sep 21 '13 at 21:54
• @RobertLewis It could also be a power of a prime – Daniel Montealegre Sep 21 '13 at 21:55
• Ah but of course! – Robert Lewis Sep 21 '13 at 21:57
• As wisdom often comes from the mouths of babes, so drivel sometimes drips from the lips of the experienced! ;) – Robert Lewis Sep 21 '13 at 21:58

Whilst staring at my laptop's screen in t'shuvah for my most blasphemous comment, grace found me, fiat lux!!!:

Let $F_q = \{a_1, a_2, . . . , a_q\}$; the $a_i$ are the distinct elements of $F_q$.

Set

$p_i(x) = f(a_i) \frac{\prod_{j \ne i}(x - a_j)}{\prod_{j \ne i}(a_i - a_j)}, \tag{1}$

then

$p_i(a_i) = f(a_i), \tag{2}$

and if $i \ne j$,

$p_i(a_j) = 0. \tag{3}$

So if we set

$P(x) = \sum_i p_i(x) \tag{4}$

it is easy to see that

$P(a_i) = f(a_i) \tag{5}$

for all $a_i \in F_q$, where as I have recently learned $F_q$ is a finite field with $q = p^n$ elements for some prime $p$!

Now, correct me if I'm wrong, did I not just rediscover (something perilously close to) Lagrange interpolation?

Ah, sweet forgiveness!

Peace, Love, and chag s'meach

But above all,

Fiat Lux!!!

• Yup, this is just Lagrange's toy, and it appears, in disguise or in all its glory, in some other answers. Yet I think your answer is nice, so חג שמח לך (let's check whether you forgto your hebrew or not) and +1 . – DonAntonio Sep 22 '13 at 3:12
• @DonAntonio, achiy! baruch l'cha! thanks for refreshing my memory in re. Lagrange's toy, I have indeed seen it around here and MO. But I really wish I knew how to write iv'riyt in my posts, how did you do that? And thanks for the echad! – Robert Lewis Sep 22 '13 at 3:40
• Thank you very very much!!! – Lullaby Sep 22 '13 at 9:26
• Glad to be of assistance!, @Lullaby – Robert Lewis Sep 22 '13 at 16:04

Try to find a polynomial that is zero everywhere except at one point $x \in F_q$. This is possible because the field is finite. The solution is a linear combination of such polynomials.

• This is really the key to the whole thing. Using my hint, it’s the easiest possible thing to write down such a polynomial for each $a$. Then you’re in business. – Lubin Sep 22 '13 at 0:27

Hint: For $\alpha \in \mathbb{F}_q$, first construct a polynomial $f_\alpha$ such that $f_\alpha(\alpha) \neq 0$ and $f_\alpha(\beta) = 0$ for all $\beta \neq \alpha$. Once this is done, you can in fact make it so $f_\alpha(\alpha) = 1$. Then the general polynomial can be made by taking a sum over the $f_\alpha$ with appropriate coefficients.

Hint: If you are familiar with the term, Lagrange Interpolating Polynomial solves the problem.

Otherwise, let $P(X)=a_nX^n+...+a_1x+a_0$ where we will chose $n$ later (I can chose it now, but the value will become obvious later).

Setting

$$P(a)=f(a) \forall a \in F_q$$ is a system of $q$ equations with the $n+1$ unknowns $a_0,...,a_n$. Thus if $n+1=q$ we get a square system, where the determinant can be proven to be non-zero (is actually a Vandermonde determinant). Pick the unique solution.

Hint: the set of nonzero elements of $\mathbb F_q$ is a group of order $q-1$. So all nonzero elements are roots of $X^{q-1}-1$. Then?