Mi ero dimenticato di questa ipotesi..
Visto che avevo già cominciato a scrivere la soluzione, dimostro che vale quel risultato se $ \displaystyle~a_k\le p_k $ per ogni k (quindi funziona anche con $ \displaystyle~a_k\le 2 $).
Intanto chiamiamo $ \displaystyle~g(P,n) $ la n-upla $ (P(0)\pmod n,\ P(1)\pmod n,\ \dots ,\ P(n-1)\pmod n) $.
Per cominciare riduciamoci al caso in cui n è potenza di primo, cioè dimostriamo che $ \displaystyle~|\{g(P,n)\}|=\prod_{k=1}^m |\{g(P,p_k^{a_k})\}| $.
Questa tesi preliminare equivale a mostrare che c'è un'associazione biunivoca tra gli elementi di $ \displaystyle~\{g(P,n)\} $ e quelli di $ \displaystyle~\{g(P,p_1^{a_1})\}\times\{g(P,p_2^{a_2})\}\times\dots\times\{g(P,p_m^{a_m})\} $. Presa quindi una n-upla $ \displaystyle~(a_1,a_2,\dots,a_n) $ del primo insieme, considero $ (a_1\pmod{p_k^{a_k}},\ a_2\pmod{p_k^{a_k}},\ \dots,\ a_{p_k^{a_k}}\pmod{p_k^{a_k}})\in\{g(P,p_k^{a_k})\} $ per ogni k, ottenendo un elemento del prodotto cartesiano.
Viceversa, a partire da m $ \displaystyle~p_k^{a_k} $-uple appartenenti ognuna al suo $ \displaystyle~\{g(P,p_k^{a_k})\} $, abbiamo per come sono definiti gli insiemi che ognuna è generata da un certo polinomio $ \displaystyle~P_k(x) $. Considero adesso il polinomio $ \displaystyle~P(x)=\sum_{i=1}^m \prod_{j\neq i} p_j^{a_j} z_i P_i(x) $, essendo $ z_i\equiv\left(\prod_{j\neq i} p_j^{a_j}\right)^{-1}\pmod{p_i^{a_i}} $. Allora $ \displaystyle~P(x)=\sum_{i=1}^m \prod_{j\neq i} p_j^{a_j} z_i P_i(x)=\sum_{i\neq k} \prod_{j\neq i} p_j^{a_j} z_i P_i(x)+\prod_{j\neq k} p_j^{a_j} z_k P_k(x)\equiv\prod_{j\neq k} p_j^{a_j} z_k P_k(x)\equiv P_k(x)\pmod{p_k^{a_k}} $ per ogni k, essendo divisibili per $ \displaystyle~p_k^{a_k} $ tutti i termini dell'ultima sommatoria. Quindi $ (P(0)\pmod{p_k^{a_k}},\ P(1)\pmod{p_k^{a_k}},\ \dots,\ P(p_k^{a_k}-1)\pmod{p_k^{a_k}}\}) $ è proprio $ (P_k(0)\pmod{p_k^{a_k}},\ P_k(1)\pmod{p_k^{a_k}},\ \dots,\ P_k(p_k^{a_k}-1)\pmod{p_k^{a_k}}\}) $, cioè la nostra associazione è sicuramente biunivoca.
Detto questo, passiamo a far vedere che $ \displaystyle~|\{g(P,p^a)\}|=p^\frac{pa(a+1)}{2} $ e avremo finito.
$ \displaystyle~|\{g(P,p^a)\}| $ è il numero di "funzioni polinomiali" $ \displaystyle~\pmod p^a $, quindi occorre capire quando due polinomi $ \displaystyle~P(x),P'(x) $ assumono gli stessi valori, ovvero quando $ \displaystyle~P(x)-P'(x) $ è la funzione che trasforma tutto in 0 $ \displaystyle~\pmod p^a $.
Consideriamo $ \displaystyle~a $ p-uple $ \displaystyle~(a_{k,0},a_{k,1},\dots,a_{k,p-1}) $ in modo che $ \displaystyle~a_{k,j}\equiv j\pmod p $ (per ogni j e k) ma allo stesso tempo anche $ \displaystyle~a_{k,j}\not\equiv a_{k',j}\pmod{p^2} $ (per ogni k, j e $ \displaystyle~j'\neq j $). Esistono: per esempio possiamo prendere $ \displaystyle~a_{k,j}=(k-1)p+j $.
Dato un polinomio $ \displaystyle~Q(x) $ tale che $ \displaystyle~\forall x\quad Q(x)\equiv0\pmod{p^a} $, abbiamo $ \displaystyle~Q(a_{1,0})\equiv0\pmod{p^a} $, quindi per Ruffini $ \displaystyle~Q(x)=(x-a_{1,0})Q'(x)+p^aRoba(x) $. Essendo $ \displaystyle~Q(a_{1,1})\equiv(a_{1,1}-a_{1,0})Q'(x)\equiv0\pmod{p^a} $, possiamo ancora dividere $ \displaystyle~Q(x) $ per $ \displaystyle~(x-a_{1,1}) $. Continuando a dividere (possiamo perché $ \displaystyle~a_{k,j}-a_{k,j'} $ è sempre invertibile), arriviamo a $ \displaystyle~Q(x)=\prod_{j=0}^{p-1}(x-a_{1,j})Q_1(x)+p^aR_0(x) $ per certi polinomi $ \displaystyle~Q_1(x) $ e $ \displaystyle~R_0(x) $ ($ \displaystyle~R_0(x) $ ha grado minore di p).
Sostituendo ora a x i vari $ \displaystyle~a_{2,j} $ otteniamo che $ \displaystyle~\prod_{j=0}^{p-1}(x-a_{1,j}) $ ha esattamente un fattore $ \displaystyle~p $, quindi $ \displaystyle~Q_1(a_{2,j})\equiv0\pmod{p^{a-1}} $ per ogni j e di nuovo possiamo dividere ottenendo $ \displaystyle~Q(x)=\prod_{j=0}^{p-1}(x-a_{1,j})\prod_{j=0}^{p-1}(x-a_{2,j})Q_2(x)+p^{a-1}\prod_{j=0}^{p-1}(x-a_{1,j})R_1(x)+p^aR_0(x) $.
Ripetendo il ragionamento con tutte le p-uple arriviamo infine al seguente mostro:
$ \displaystyle~Q(x)=\sum_{i=0}^a p^{a-i}\prod_{k=1}^i\prod_{j=0}^{p-1}(x-a_{k,j})R_i(x) $.
Viceversa è facile vedere che ogni $ \displaystyle~Q(x) $ del genere, al variare dei polinomi $ \displaystyle~R_i(x) $, è sempre nullo considerato come funzione:
- per $ \displaystyle~R_a(x)=1 $ e $ \displaystyle~R_i(x)=0 $ per ogni $ \displaystyle~i\neq a $ otteniamo il polinomio $ \displaystyle~S_a(x)=\prod_{k=1}^a\prod_{j=0}^{p-1}(x-a_{k,j}) $, monico e di grado $ \displaystyle~pa $;
- per $ \displaystyle~R_{a-1}(x)=1 $ e $ \displaystyle~R_i(x)=0 $ per ogni $ \displaystyle~i\neq a-1 $ otteniamo $ \displaystyle~S_{a-1}(x)=p\prod_{k=1}^{a-1}\prod_{j=0}^{p-1}(x-a_{k,j}) $, con coeff. direttivo $ \displaystyle~p $ e di grado $ \displaystyle~p(a-1) $;
- ...
- per $ \displaystyle~R_1(x)=1 $ e $ \displaystyle~R_i(x)=0 $ per ogni $ \displaystyle~i\neq 1 $ si ha $ \displaystyle~S_1(x)=p^{a-1}\prod_{j=0}^{p-1}(x-a_{1,j}) $, con coeff. direttivo $ \displaystyle~p^{a-1} $ e di grado $ \displaystyle~p $.
Con questi polinomi "nulli" particolari, possiamo ridurre un polinomio $ \displaystyle~P(x)=\sum_{i=0}^d c_i x^i $ qualsiasi a uno identico come funzione ma di grado minore di $ \displaystyle~pa $ (togliendo un opportuno multiplo di $ \displaystyle~S_a(x) $) e con i coefficienti che rispettano le condizioni $ \displaystyle~0\le c_i<p^{a-k} $ per ogni $ \displaystyle~kp\le i<(k+1)p $ e per ogni k (aggiustando i coefficienti dal grado più alto fino a $ \displaystyle~c_0 $, togliendo un opportuno multiplo di $ \displaystyle~x^{i-kp}S_k(x) $ per $ \displaystyle~kp\le i<(k+1)p $).
A questo punto le funzioni polinomiali $ \displaystyle~\pmod{p^a} $ sono al massimo il numero di polinomi di questo tipo, che è proprio $ \displaystyle~(p^a)^p(p^{a-1})^p\cdots p^p=p^{p(1+2+\dots+(a-1)+a)}=p^\frac{pa(a+1)}{2} $.
Ma in effetti se per assurdo due polinomi distinti $ \displaystyle~P(x),P'(x) $ di questo tipo fossero uguali come funzioni avremmo che $ \displaystyle~P(x)-P'(x)=\sum_{i=0}^{pa-1}(c_i-c_i')x^i $ sarebbe della forma $ \displaystyle~Q(x)=\sum_{i=0}^a p^{a-i}\prod_{k=1}^i\prod_{j=0}^{p-1}(x-a_{k,j})R_i(x) $, ma è facile vedere che $ \displaystyle~|c_i-c_i'|<p^k (*) $ (per $ \displaystyle~kp\le i<(k+1)p $ e per ogni k). Dunque, chiamando N il più grande $ \displaystyle~i $ tale che $ \displaystyle~R_i(x)\neq 0 $, notando che i polinomi $ \displaystyle~p^{a-i}\prod_{k=1}^i\prod_{j=0}^{p-1}(x-a_{k,j})R_i(x) $ hanno grado minore di $ \displaystyle~pi+p<pN $ per $ \displaystyle~i<N $ e che $ \displaystyle~p^{a-N}\prod_{k=1}^N\prod_{j=0}^{p-1}(x-a_{k,j})R_N(x) $ ha grado $ \displaystyle~\ge pN $, il termine di grado massimo di $ \displaystyle~Q(x) $ appartiene a quest'ultimo e ha quindi coefficiente non nullo e multiplo di $ \displaystyle~p^{a-N} $. Ma questo coefficiente è $ \displaystyle~c_i-c_i' $ per qualche $ \displaystyle~i\ge pN $, assurdo per la $ \displaystyle~(*) $.
Chiedo scusa per la dimostrazione prolissa e per la notazione complicata e aspetto conferme..