Linear Map = Function of degree P-1

[brru25]

If p is prime, prove that for every function f: F_p -> F_p there exists a polynomial Q (depending on f) of degree at most p-1 such that f(x) = Q(x) for each x in F_p.

 

[brru25]

Would polynomial interpolation work here?

 

[HallsofIvy]

I don't see how you could interpolate. There are only p possible values in F_p. I notice you titled this "Linear Map= Function of degree P-1". Do you understand that there is nothing said here about f being linear?

 

[brru25]

Yea I assumed by accident it was linear. Yea I understand that there are only p values in Fp but I don't know how to make the connection to a polynomial. I mean I know a polynomial of degree p-1 has p coefficients but for some reason I can't connect the dots.

 

[Hurkyl]

Would polynomial interpolation work here?

Have you tried it? What happened?

I don't see how you could interpolate.

Polynomial interpolation works over any field... or is there something else you see that I don't?

 

[HallsofIvy]

Polynomial interpolation works over any field... or is there something else you see that I don't?

Well, I think of "interpolation" as finding values between given values. And since this is a finite field, there is nothing "between" values.

 

[Hurkyl]

Well, I think of "interpolation" as finding values between given values. And since this is a finite field, there is nothing "between" values.

http://en.wikipedia.org/wiki/Polynomial_interpolation