wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> putnam exam (pure math) >> polynomial of degree n
        
(Message started by: BenVitale on Jan 28^th, 2008, 8:25pm)

Title: polynomial of degree n
Post by BenVitale on Jan 28^th, 2008, 8:25pm

If f(x) is a polynomial of degree n, prove that f(x)=0(mod p) has exactly n solutions if and only if f(x) divides x^p -x (mod p).

Title: Re: polynomial of degree n
Post by Obob on Jan 29^th, 2008, 1:28am

The main idea is to note that [hide]every element of Z/pZ is a root of x^p-x[/hide]

Title: Re: polynomial of degree n
Post by BenVitale on Jan 29^th, 2008, 1:40pm

Obob,

Well it's easy to show that if f(x) is a factor of x^p -x(mod p), of degree n, then f(x) has exactly n solutions, however I don't know how to prove the converse (ie if f(x) is of degree n and has n solutions then
f(x) divides x^p -x(mod p).

Title: Re: polynomial of degree n
Post by Obob on Jan 29^th, 2008, 6:12pm

If say a is a root of f(x) (mod p), then x-a divides f(x) (mod p). Prove this using the division algorithm for polynomials. So f(x) factors as a product c(x-a₁)...(x-a_n) for some number c, where the a_i are the roots of f(x). But by the same logic, x^p-x factors as x(x-1)(x-2)...(x-(p-1)). Hence f(x) divides x^p-x.

Title: Re: polynomial of degree n
Post by BenVitale on Jan 31^st, 2008, 9:06pm

Oh yeah, I forgot that you could do things like that. Man, it wasn't really that difficult after all was it.

Thank you very much.