My own - Somme, residui quadratici e coefficienti binomiali

[HiTLeuLeR]

Per ogni $ n \in \mathbb{N} $ ed ogni $ k = 0, 1, \ldots, n $, sia $ \displaystyle C^k_n = \binom{n}{k} = \frac{n!}{k! (n-k)!} $. Essendo $ p \in \mathbb{N} $ un primo $ \ge 3 $ ed $ a $ un intero, sia quindi $ \displaystyle \left(\frac{a}{p}\right) = 1 $, se $ a $ è un residuo quadratico mod $ p $; $ \displaystyle \left(\frac{a}{p}\right) = - 1 $, se $ a $ non è un residuo quadratico mod $ p $; e infine$ \displaystyle \left(\frac{a}{p}\right) = 0 $, se $ a $ è divisibile per $ p $. Su queste premesse:

"Valutare l'espressione $ \displaystyle \sum_{k=0}^{p-1} \left(\frac{C_{p-1}^k}{p}\right) $, quando $ p = 17449 $ oppure $ p = 4239974339 $, noto che in entrambi i casi $ p $ è un numero primo. BONUS QUESTION: come generalizzare il risultato del calcolo?"

[edriv]

Io intanto provo questo esercizio con qualche osservazione:
- noto che entrambi i primi finiscono per 9
- entrambi hanno almeno una cifra ripetuta nella rappresentazione decimale.

Poi non saprei andare avanti... se qualcuno vuole proseguire da dove sono arrivato io, lo faccia pure.

[barbastyle]

ciao a tutti... è il primo messaggio che mando... forse ci vedremo spesso...

c'è un teorema (che non ho idea di come si dimostri) che dice: "essendo p un numero primo dispari metà dei numeri a: 0,1,2...p-1 sono residi quadratici modulo p"
quindi risulta (con la condizione che p sia un numero primo dispari) che per metà dei valori risulterà 1-1/p che è quindi uguale a zero e per l'altra metà -2/p... quindi il risultato della sommatoria è p/2 (che sono il numero degli addendi non nulli (da 0 a p-1) che moltiplica -2/p che risulta -1...

[TADW_Elessar]

Provo a vedere se le mie idee aiutano qualcun altro, io sono ko.

Innanzitutto, direi che nessuno dei valori nella sommatoria è zero, poiché:

$ \displaystyle \binom{p-1}{k} = \frac{(p-1)(p-2) \cdots (p-k)}{k!} $, ma $ ~p $, essendo più grande di tutti i fattori al numeratore, non comparirà nella scomposizione in fattori primi di $ ~C_{p-1}^k $, quindi credo che si possa concludere che $ \displaystyle 0 \leq k \leq p-1 \Rightarrow p \nmid \binom{p-1}{k} \Rightarrow \bigg(\frac{C_{p-1}^k}{p}\bigg) \neq 0 $.

Ora, visto che nella sommatoria compaiono $ ~p $ addendi, nessuno dei quali nullo (se quanto ho scritto sopra ha senso), basta contare quanti valgano uno. Ho pensato che si potesse risolvere con il criterio di Eulero, ovvero riformulando la domanda come:

Per quanti $ ~k $ si ha che $ \displaystyle \binom{p-1}{k}^{\frac{p-1}{2}} \equiv 1 \pmod{p} $?

[piever]

Io intanto provo questo esercizio con qualche osservazione:
- noto che entrambi i primi finiscono per 9
- entrambi hanno almeno una cifra ripetuta nella rappresentazione decimale.

Poi non saprei andare avanti... se qualcuno vuole proseguire da dove sono arrivato io, lo faccia pure.

Uhm, diciamo che f(n) e' definito in questo modo per n intero positivo: prendo la scrittura in base dieci di n e sommo le cifre, poi riscrivo cio' che ho ottenuto in base dieci e sommo le cifre e cosi' via finche' non ottengo un numero minore di 10 (questa cosa e' anche chiamata congruenza modulo 9).

Ora mi sembra della massima rilevanza che:

$ f(17449)f(4239974339)=\sigma (\frac{f(17449)f(4239974339)}{2}) $

Dove $ \sigma (\cdot ) $ e' la somma dei divisori di un numero.

Infatti si verifica la seguente cosa:

Poniamo:

$ \displaystyle \sum_{k=0}^{17448} \left(\frac{C_{17448}^k}{17449}\right)=a $

$ \displaystyle \sum_{k=0}^{4239974338} \left(\frac{C_{4239974338}^k}{4239974339}\right)=b $

Dimostrare che:

$ f(a)f(4239974339b)=\sigma (\frac{f(a)f(4239974339b)}{2}) $


EDIT: chiedo umilmente scusa a HiTLeuLeR per essere intervenuto cosi' a sproposito nel suo thread, non mi ero reso conto che 4239974339 non e' congruo a 1 modulo 4, quindi la relazione finale che avevo scritto prima era falsa, ho provveduto a correggere.

[HiTLeuLeR]

Rimosso. -- EG

[TADW_Elessar]

Che cattivoni.

Veramente diabolico.

[HiTLeuLeR]

Rimosso. -- EG

@TADW_Elessar: ci può stare, è comunque una strada. Solo bisogna approfondirla.

[EvaristeG]

Ricordiamo inoltre che tra le regole (forse anche del forum, ma sicuramente della buona creanza) c'è quella di non offendere gli altri utenti sulla base delle eventuali risposte sbagliate o incomplete, oppure per il fatto che non abbiano capito un problema, una soluzione o un'osservazione.
Pertanto, prego HiTLeuLeR di moderare i toni e di autocensurarsi, limitando gli interventi alla parte matematica della questione.

Grazie

[TADW_Elessar]

Incredibile! Aprendo il libro di teoria dei numeri a caso è venuto fuori questo problema:

Dimostra che per ogni numero primo $ ~p $ e ogni $ ~k \quad (0 \leq k \leq p-1) $,
$ \displaystyle \binom{p-1}{k} \equiv (-1)^k \pmod{p} $. Per ora non ho nemmeno provato a risolverlo, ma sostituendo nella congruenza che ho scritto sopra:

Per quanti dei p k vale la seguente congruenza? $ \displaystyle \binom{p-1}{k}^{\frac{p-1}{2}} \equiv [(-1)^k]^{\frac{p-1}{2}} \equiv 1 \pmod{p} $

Se $ ~(p-1)/2 $ è ancora pari (per esempio con p = 17449), il segno di $ ~(-1)^k $ non importa perché l'altro esponente pari rende vera l'uguaglianza per tutti i k. Poiché quindi tutti i termini nella sommatoria sono +1, si può concludere che:

$ \displaystyle \sum_{k=0}^{17448} \bigg(\frac{C_{17448}^k}{17449}\bigg) = 17449 $.

Ora mi metto al lavoro sull'altro caso, senza contare che c'è da dimostrare quella robetta qui sopra

[HiTLeuLeR]

Rimosso. -- EG

Incredibile! Aprendo il libro di teoria dei numeri a caso è venuto fuori questo problema:

Dimostra che per ogni numero primo $ ~p $ e ogni $ ~k \quad (0 \leq k \leq p-1) $: $ \displaystyle \binom{p-1}{k} \equiv (-1)^k \mod p $.

Esattamente! Pensa che la dimostrazione sta già sul forum...

[EvaristeG]

Ok, basta.

[TADW_Elessar]

Esattamente! Pensa che la dimostrazione sta già sul forum...

Dove? Dove?

Comunque il resto ora è facile. Per $ ~p \mbox{ tale che \`{e} troppo grande per scriverlo senza sbagliare e } (p-1)/2 $ è dispari, l'esponente $ 0 \leq k \leq p-1 $ sarà nell'intervallo $ ~(p+1)/2 $ volte pari e $ ~(p-1)/2 $ dispari. Perciò la somma sarà:

$ \displaystyle \sum_{k=0}^{p-1} \bigg(\frac{C_{p-1}^k}{p}\bigg) = \frac{p+1}{2} - \frac{p-1}{2} = 1 $.

Giusto?

[HiTLeuLeR]

Per $ (p-1)/2 $ [che] è dispari, l'esponente $ 0 \leq k \leq p-1 $ sarà nell'intervallo $ ~(p+1)/2 $ volte pari e $ ~(p-1)/2 $ dispari. Perciò la somma sarà:

$ \displaystyle \sum_{k=0}^{p-1} \bigg(\frac{C_{p-1}^k}{p}\bigg) = \frac{p+1}{2} - \frac{p-1}{2} = 1 $.

Giusto?

Sì, giusto.