Author |
Topic: polynomial of degree n (Read 1136 times) |
|
Benny
Uberpuzzler
Gender: 
Posts: 1024
|
 |
polynomial of degree n
« on: Jan 28th, 2008, 8:25pm » |
 Quote  Modify
|
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).
|
|
 IP Logged |
If we want to understand our world — or how to change it — we must first understand the rational choices that shape it.
|
|
|
Obob
Senior Riddler
Gender:
Posts: 489
|
|
Re: polynomial of degree n
« Reply #1 on: Jan 29th, 2008, 1:28am » |
Quote Modify
|
The main idea is to note that every element of Z/pZ is a root of xp-x
|
|
IP Logged |
|
|
|
Benny
Uberpuzzler
Gender:
Posts: 1024
|
|
Re: polynomial of degree n
« Reply #2 on: Jan 29th, 2008, 1:40pm » |
Quote Modify
|
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).
|
|
IP Logged |
If we want to understand our world — or how to change it — we must first understand the rational choices that shape it.
|
|
|
Obob
Senior Riddler
Gender:
Posts: 489
|
|
Re: polynomial of degree n
« Reply #3 on: Jan 29th, 2008, 6:12pm » |
Quote Modify
|
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-a1)...(x-an) for some number c, where the ai are the roots of f(x). But by the same logic, xp-x factors as x(x-1)(x-2)...(x-(p-1)). Hence f(x) divides xp-x.
|
|
IP Logged |
|
|
|
Benny
Uberpuzzler
Gender:
Posts: 1024
|
|
Re: polynomial of degree n
« Reply #4 on: Jan 31st, 2008, 9:06pm » |
Quote Modify
|
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.
|
|
IP Logged |
If we want to understand our world — or how to change it — we must first understand the rational choices that shape it.
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print