# Homework Help: Linear Map = Function of degree P-1

1. Oct 26, 2009

### brru25

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

2. Oct 29, 2009

### brru25

Would polynomial interpolation work here?

3. Oct 29, 2009

### 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?

4. Oct 29, 2009

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

5. Oct 29, 2009

### Hurkyl

Staff Emeritus
Have you tried it? What happened?

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

6. Oct 30, 2009

### HallsofIvy

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

7. Oct 30, 2009

### Hurkyl

Staff Emeritus