p|f(a_1,a_2,...,a_m),problema 4

[jordan]

Sia $ m $ un intero positivo e $ p $ un numero primo, entrambi fissati. Sia $ S $ l'insieme di tutte le $ m $-uple di interi positivi $ \vec{v}=(v_1,v_2,\ldots,v_m) $ tali che $ 1 \le v_i \le p $ per ogni $ 1 \le i \le m $. Definiamo inoltre la funzione $ f(\cdot):\mathbb{N}^m \to \mathbb{N} $, che associa a ogni $ m $-upla di interi non negativi $ (a_1,a_2,\ldots,a_m) $ l'intero $ \displaystyle f(a_1,a_2,\ldots,a_m)=\sum_{\vec{v} \in S} \left(\prod_{1 \le i \le m}{v_i^{a_i}} \right) $. Trovare tutte le $ m $-uple di interi non negativi $ (a_1,a_2,\ldots,a_m) $ tali che $ p \mid f(a_1,a_2,\ldots,a_m) $.
(Pierfrancesco Carlucci)

[karlosson_sul_tetto]

E il quinto...

[exodd]

tramite double counting,
$ \sum(\prod{v_i^{a_i}})=\prod(1^{a_i}+2^{a_i}+...+p^{a_i}) $
dove $ 1^{a_i}+2^{a_i}+...+p^{a_i} $ è divisibile per p per ogni $ \displaystile{a_i} $ non multiplo di p-1
quindi vanno bene tutte le m-uple che hanno almeno un $ \displaystile{a_i} $ non multiplo di p-1

[dario2994]

Stesso identico modo... ma poi per dimostrare il secondo lemmino mi ci sono impiccato... poi l'ho fatto coi generatori modulo p È la prima volta che li uso... quindi non sono sicuro di aver fatto bene xD

p.s. comunque vanno anche bene le m-uple con un elemento nullo

[kn]

@exodd: e non nullo

[exodd]

e vabbè....

[jordan]

Ok, tocca a me scriverla per bene

Trovare tutte le $ m $-uple di interi non negativi $ (a_1,a_2,\ldots,a_m) $ tali che $ p \mid f(a_1,a_2,\ldots,a_m) $.
(Pierfrancesco Carlucci)

Abbiamo che $ \displaystyle f(a_1,a_2,\ldots,a_m)=\sum_{\vec{v} \in S} \left(\prod_{1 \le i \le m}{v_i^{a_i}} \right)=\prod_{1 \le i \le m}{\left(\sum_{1 \le k \le p}{k^{a_i}}\right)} $. Se $ a=0 $ allora banalmente $ \displaystyle p \mid p=\sum_{1 \le k \le p}{k^a} $ e se $ \displaystyle p-1 \mid a>0 $ allora $ \displaystyle \sum_{1 \le k \le p}{k^a}=-1 $ in $ \mathbb{F}_p $. In tutti gli altri casi, detto $ g $ un generatore in $ \mathbb{F}_p^* $ vale $ \displaystyle \sum_{1 \le k \le p}{k^a}=\sum_{0 \le l \le p-2}{g^{al}}=\frac{g^{a(p-1)}-1}{g^a-1} \equiv 0 \pmod p $, dato che $ \displaystyle g^a-1 $ è invertibile in $ F_p $. Segue direttamente che $ \displaystyle p \mid f(a_1,\ldots,a_n) $ se e solo se $ \displaystyle (a_1,\ldots,a_n) \in \mathbb{N}^m \setminus ((p-1)\mathbb{N}_0)^m $.[]