Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
1  
Hint: $f(\alpha)\neq 0$ if $f(x) = (x-\alpha) +1$. –  John Dec 12 '13 at 8:22
1  
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

3 Answers 3

up vote 2 down vote accepted

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
share|improve this answer
    
Thank you, very nicely explained –  Heidi.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 –  Heidi.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$ ? –  Heidi.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?

share|improve this answer
1  
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? –  Heidi.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$ –  Heidi.E Dec 12 '13 at 11:23
1  
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".

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.