veelterm

Opgave - APMC 2002 dag 2 vraag 2

Stel $A=\{2,7,11,13\}$. Een veelterm $f$ met gehele coëfficiënten bezit de volgende eigenschap: voor ieder geheel getal $n$ bestaat er een $p\in A$ zodat $p|f(n)$. Bewijs dat er een $p\in A$ bestaat zodat $p|f(n)$ voor alle $n$.

Oplossing

Observatie vooraf: $x\equiv y \mod{p} \Rightarrow f(x)\equiv f(y) \mod{p}$ voor alle gehele $x,y$ en $p$. Dit volgt uit de deelbaarheidsketen $p\mid x-y \mid f(x)-f(y)$ want dit laatste is altijd geldig voor veeltermen met gehele coëfficiënten. We zullen dit lemma in de oplossing gebruiken.

Stel nu dat het tegengestelde waar is: voor alle $p\in A$ zou dan gelden dat er een $a_p$ bestaat zodanig dat $p\nmid f(a_p)$. Met andere woorden, geen enkele $p$ deelt alle beeldwaarden van $f$.

Kies nu $x$ zodanig dat $x\equiv a_p \mod{p}$ voor alle $p\in A$. Zo'n $x$ bestaat wel degelijk wegens de Chinese reststelling en aangezien alle elementen in $A$ copriem zijn. Dit betekent dat $f(x)\equiv f(a_p) \not\equiv 0 \mod{p}$ dus $p\nmid f(x)$ voor alle $p\in A$. Maar dit is duidelijk in strijd met het gegeven, a.k.a. de stelling is bewezen.
$\square$

Noot: het is zeer makkelijk dit te veralgemenen naar willekeurige, eindige verzamelingen $A$ met elementen onderling copriem (mijn oplossing gebruikt de getallen $2,7,11,13$ niet eens). Na een klein beetje meer moeite kunnen we dit zelfs bewijzen voor willekeurige , eindige verzamelingen gehele getallen.