polynomial over a finite field

Question

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?

Answer 1

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

Answer 2

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?

Answer 3

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".