veelterm modulo p
Opgave - IMOSL 1997 vraag 12
Zij $p$ een priemgetal en $f(x)$ een veelterm van graad $d$ met gehele coëfficiënten zodat $f(0)=0$ en $f(1)=1$ en voor ieder natuurlijk getal $n$ is de rest bij deling van $f(n)$ door $p$ gelijk aan 0 of 1. Bewijs dat $d\geq p-1$.
- login om te reageren
Oplossing
Opnieuw een pareltje.
Stel de graad van $f$ is hoogstens $p - 2$.
Lemma: Als $k \leq p - 2$ geldt dat $1^k + 2^k + \cdots + (p - 1)^k$ deelbaar is door $p$.
Bewijs: kan met inductie, maar er is een leuker alternatief. Zij $\lambda$ een primitieve wortel modulo $p$, dan is $$1^k + 2^k + \cdots + (p - 1)^k = 1 + \lambda^k + \cdots + \lambda^{k(p - 2)} = \frac{\lambda^{k(p - 1) } - 1}{\lambda^k - 1} \equiv 0 \pmod{p}.$$
Als $\deg f \leq p - 2$ geldt dus (volgens het lemma!) dat $f(0) + f(1) + f(2) + \cdots + f(p - 1) \equiv 0 \pmod{p}$...
maar dat kan niet, want $f(0) = 0$, $f(1) = 1$ en $f(j) \equiv 0 \pmod{p}$ of $f(j) \equiv 1 \pmod{p}$ voor alle $j$.