Più umano, più vero: il teorema di Lucas

[piever]

Buondì a tutti: è molto che non posto su questo forum, mi fa piacere sapere che ha riaperto e anche che la sezione TdN è particolarmente attiva e girano parecchi problemi interessanti e niente affatto banali.

Ho sbirciato nella staffetta e ho visto comparire un paio di cose collegate al teorema di Lucas e una sua dimostrazione un pochino contosa, volevo proporvene una un pochino più concettuale.

Th. Lucas: Siano $ \displaystyle a=\sum_{i=0}^k a_ip^i $ e $ \displaystyle b=\sum_{i=0}^k b_ip^i $ due interi positivi con le rispettive rappresentazioni in base p (vale a dire $ 0\le a_i,b_i<p $), con p primo. Si dimostri che

$ \displaystyle\binom{a}{b}\equiv\prod_{i=0}^k\binom{a_i}{b_i}\pmod p $

usando la definizione di $ \displaystyle\binom{a}{b} $ come coefficiente del termine di grado b del polinomio $ (1+x)^a $

Chi vuole, provi a usare la stessa strategia per dimostrare il bel problema di kn: dato p primo maggiore di 3, allora $ \displaystyle\binom{a}{b}\equiv\binom{pa}{pb}\pmod{p^3} $

Buon lavoro.

[jordan]

Ciao Pietro, chi si rivede
Non ti brucio il problema, dopo che finalmente sei riuscito a postarne uno "umano" xd

[dario2994]

Uhm... provo con una dimostrazione più sincera, ma mi sa che non è quella a cui ti riferisci (nel senso che pure questa è un poco contosa )
Bon... do per scontato che $p$ divide tutti i coef di $(x+1)^{p^i}-x^{p^i}-1$ (non mi viene in mente nessun modo "polinomiale" o combinatorico per dimostrarla... ) ma allora divide anche tutti i coef di $\displaystyle (x+1)^{a_ip^i}-(x^{p^i}+1)^{a_i}$ (perchè il primo polinomio divide algebricamente il secondo).
Da questo ricavo 2 fatti che uso poi implicitamente:
$\displaystyle p^i\nmid m\Rightarrow p|[x^m](x+1)^{p_ia^i}$
$\displaystyle m=p^ib_i \Rightarrow [x^m](x+1)^{a_ip^i}\equiv [x^m](x^{p^i}+1)^{a_i}\equiv [x^{b_i}](x+1)^{a_i}\equiv \binom{a_i}{b_i}\pmod{p}$

E ora la botta di latex:
$\displaystyle \binom{a}{b}\equiv [x^b](x+1)^a\equiv [x^b]\prod_{i=0}^k(x+1)^{a_ip^i}\equiv \sum_{m_0+m_1+\dots+m_k=b}\prod_{i=0}^k[x^{m_i}](x+1)^{a_ip^i}\equiv \sum_{m_0+\dots m_k=b\wedge\ \forall j\ p^j|m_j}\prod_{i=0}^k[x^{m_i}](x+1)^{a_ip^i}\equiv \prod_{i=0}^k[x^{b_ip^i}](x+1)^{a_ip^i}\equiv \prod_{i=0}^k\binom{a_i}{b_i}\pmod{p}$

Non so quanto sia chiero

[piever]

Uhm, è più sincera, ma attenzione, alcuni passaggi si possono ancora rendere più umani e più veri, lavorando in $ \mathbb{Z}_p $ (che è un campo per chi sa cosa intendo, dunque tutto va per il meglio):

$ (1+x)^p=(1+x^p) $ (come polinomi di $ \mathbb{Z}_p[x] $) visto che gli altri coefficienti moltiplicano binomiali evidentemente multipli di p.

Dunque, iterandola di volta in volta con $ \displaystyle y=x^{p^{i-1}} $, ottengo $ \displaystyle (1+x)^{p^i}=(1+x^{p^i}) $ che, se la elevo alla $ a_i $ mi dà: $ \displaystyle (1+x)^{a_ip^i}=(1+x^{p^i})^{a_i} $

Ora anche la botta di LaTeX (spero non di latex...) dovrebbe divenirti più chiara e più facile da seguire: tutti i "coefficiente di grado b congruo a" diventano delle banali uguaglianze tra polinomi a coeffficienti in $ \mathbb{Z}_p $...

Ora se vuoi puoi provare a fare il problema di kn in quest'ottica: la tesi è diventata che i termini di $ (1+x)^{ap}-(1+x^p)^a $ di grado multiplo di p hanno coefficienti multipli di $ p^3 $

[dario2994]

$ (1+x)^p=(1+x^p) $ (come polinomi di $ \mathbb{Z}_p[x] $) visto che gli altri coefficienti moltiplicano binomiali evidentemente multipli di p.
Dunque, iterandola di volta in volta con $ \displaystyle y=x^{p^{i-1}} $, ottengo $ \displaystyle (1+x)^{p^i}=(1+x^{p^i}) $ che, se la elevo alla $ a_i $ mi dà: $ \displaystyle (1+x)^{a_ip^i}=(1+x^{p^i})^{a_i} $

Questo non mi veniva in mente

botta di LaTeX (spero non di latex...)

(c'avevo anche pensato scrivendolo... ma non pensavo che qualcun altro ci pensasse )