# polynomial over a finite field

Show that in a finite field $F$ there exists $p(x)\in F[X]$ s.t $p(f)\neq 0\;\;\forall f\in F$

Any ideas how to prove it?

-
Hint: $f(\alpha)\neq 0$ if $f(x) = (x-\alpha) +1$. – John Ma Dec 12 '13 at 8:22
It might look better if you replace your $f\in F$ with $\alpha \in F$ as usually we write $f$ for functions... – Praphulla Koushik Dec 12 '13 at 8:35

Take some element $\alpha_1\in F$

Then consider $f_1(x)=(x-\alpha_1)+1$.. What would be $f_1(\alpha_1)$?

Soon you will see that $f(\alpha_1)$ is non zero but may probably for some $\alpha_2$ we have $f_1(\alpha_2)=0$

Because of this i would now try to include $(x-\alpha_2)$ in $f_1(x)$ to make it

$f_2(x)=(x-\alpha_1)(x-\alpha_2)+1$.. What would be $f_1(\alpha_1),f _2(\alpha_2)$?

keep doing this until you believe that resultant function does not have a root in $F$.

You have two simple questions :

• will the resultant be a polynomial in general if you repeat this steps.
• How do you make sure that no element in field is a root of resultant
-
Thank you, very nicely explained – H.E Dec 12 '13 at 8:53
You are welcome but this is not yet done.... :D – Praphulla Koushik Dec 12 '13 at 8:55
yes, I know. I thought about the first question: the result will be a polynomial, also the field is finite so we will have finitely many such linear factors. But I am not sure how to answer the second one – H.E Dec 12 '13 at 8:57
suppose you have one more element in the field which is a root of resultant polynomial... what would you do? – Praphulla Koushik Dec 12 '13 at 8:58
won't all the linear factors become zero then and we will be only left with the constant $1$ ? – H.E Dec 12 '13 at 9:04

Let $p(x)=1$, you win. Here's a less stupid example with the same flavor. If $|F|=q$, then consider $x^q-x+1$. Can you figure out why you still win?

-
if $|F|=q$ then for any $f\in F$ we have that $f^{q}=f$ so $x^{q}-x+1=x-x+1=1\neq 0$ Is it enough? – H.E Dec 12 '13 at 8:37
Right that's it. There are other examples where the polynomial is nonconstant in the sense that it outputs different values for different inputs. For example, if $q \equiv 3 \pmod 4$, then $x^2+1$ will work. – Dylan Yott Dec 12 '13 at 8:43
I do have a question: Why $q$ must be $\equiv 3\pmod 4$? so that $x^2+1$ will work??? For example in $\mathbb{Z}_{2}$ this polynomial will have zero at $x=1$ – H.E Dec 12 '13 at 11:23
Dot those $p$'s and $q$'s $+\left(\frac{p^*}{q}\right)\left(\frac{q}{p}\right)$ – Stahl Dec 12 '13 at 17:45

Consider counting the total number of monic polynomials with roots, for fixed degree : say for degree $3$ , you can have $(x-r_1)(x-r_2)(x-r_3)$ (notice that you need to consider that different permutations of $r_1,r_2,r_3$ will generate the same polynomial). And the overall number of monic polynomials will be $x^3+ax^2+bx+c$ , where (hint) $(a,b,c)$ is in $\mathbb F^3$.

EDIT: The identity I had in mind was: for degree q<|$\mathbb F$| , there are $\mathbb FCq$ ways of having all different roots, then, for having 1 repeat....1 way of having all roots equal, compared with |$\mathbb F^3$|. Even for $q=2$, we have $\mathbb FC2$+|$\mathbb F$| , versus |$\mathbb F^2$|, where the $C$ means "choose".

-