OliForum Matematico

allora, vi do una ricetta:
ingredienti:
- un numero primo, $ p $;
- due polinomi $ a,b $ a coefficienti in $ \mathbb{Z}/p\mathbb{Z} $, che sono $ a(x)=x+1, b(x)=x^{p-2}+x^{p-3}+\dots+x^2+2x+1 $.
preparazione:
presi due polinomi $ f,g $ che ho a disposizione (o perché sono ingredienti, o perché li ho preparati), li posso comporre (ovvero prendere il polinomio $ f(g(x)) $ e poi prenderne il resto della divisione per $ x^p-x $.*

se ogni persona può mangiare un polinomio, quante persone potete sfamare con questa ricetta?

[dall'IMC 2009]

* in questo modo non necessariamente preparo $ f(g(x)) $, ma solo il polinomio-resto.

$ a(x) $ e $ b(x) $ sono entrambi bigezioni, in particolare $ p|a(x_0)-(x_0+1) $ per ogni $ x_0 \in \mathbb{Z} $, $ b(0)=1, b(1)=0 $ e $ p|b(x_0)-x_0 $ per ogni intero $ 2 \le x_0 \le p-1 $, per cui la prima funzione effettua uno "shift" ai residui, la seconda invece li lascia invariati eccetto che "scambiare" 0 e 1. Le composizioni di bigezioni sono chiaramente bigezioni e partendo da $ \{0,1,...,p-1\} $ possiamo ottenere qualunque altra sua permutazione componendo in vario modo le due funzioni precedenti. Il discorso che diciamo della bigezione rispetto ai residui è lecito, infatti se un polinomio $ W(x) $ è diviso per $ x^p-x $ allora, detto $ w(x) $ il polinomio resto, si avrà $ W(x_0) \equiv w(x_0) \pmod p $per ogni $ x_0 \in \mathbb{Z} $. Inoltre i polinomi che possiamo ottenere hanno tutti grado minore di $ p $ (visto che sono resti rispetto a un polinomio monico di grado $ p $, e perciò due set di permutazioni non possono coincidere in due polinomi distinti). Ciò significa che posso sfamare $ p! $ persone.