Primi e binomiali

[HiTLeuLeR]

Problema #1 (teorema di Gosper): mostrare che, se $ q\in\mathfrak{P}\!\setminus\!\{2\} $: $ \displaystyle{\binom{q-1}{\frac{q-1}{2}}\equiv(-1)^{\frac{q-1}{2}}\bmod q} $.

[HiTLeuLeR]

Boh, con ogni rispetto per Gosper, ma il suo teorema mi pare proprio una grande cagata...

Generalizzando il teorema di Gosper: C.N.S. affinché un intero $ n > 1 $ sia primo in $ \mathbb{N} $ è che, per ogni $ k = 0, 1, \ldots, n-1 $: $ \displaystyle{\binom{n-1}{k}\equiv (-1)^k \bmod n} $.

Ok, ne reclamo la paternità! Qualcuno dimostri ch'è banale, altrimenti mi monterò la testa...

[gip]

Dimostro innanzitutto che se n è primo allora vale quella relazione.
Si ha che $ \binom{n-1}{k}=\frac{(n-1)!}{k!(n-1-k)!} $ .
Lavoriamo nel campo degli interi mod n: il numeratore di quella frazione è dato dal prodotto tra tutti gli elementi (diversi da 0) del campo e varrà quindi -1, poiché è dato dal prodotto di n-1 (congruo a -1) e di tutti i numeri da 2 a n-2, che sono a coppie l'uno l'inverso dell'altro (poichè ogni elemento deve avere uno ed un solo inverso, e non è possibile che un elemento tra quelli sia l'inverso di se stesso, altrimenti, chiamatolo t, si avrebbe $ t^{2}\equiv1 $, ossia $ t^{2}-1\equiv 0 $, da cui n non primo, assurdo).
Il denominatore è dato dal prodotto tra i k elementi più piccoli e gli n-1-k elementi più piccoli, che è uguale (a meno del segno qualora $ \frac{n-1}{2} $ e k abbiano differente parità) al prodotto dei quadrati degli $ \frac{n-1}{2} $ elementi più piccoli; questo insieme di quadrati forma a sua volta un gruppo rispetto alla moltiplicazione (come è facile dimostrare), e il prodotto dei suoi elementi sarà -1 o 1 a seconda che abbia un numero di elementi pari o dispari, visto che anch'essi sono l'uno l'inverso dell'altro a coppie, tranne l'1 ed il caso -eventuale- del -1 (che è appunto presente se e solo se il numero di elementi è pari). Il numero di elementi di questo ultimo gruppo è uguale a $ \frac{n-1}{2} $. In definitiva dunque il denominatore vale 1 se k è dispari e -1 se k è pari, quindi l'intero coeff. binomiale vale 1 per k pari e -1 per k dispari. CVD

Dimostro ora che se n non è primo, allora quella relazione non vale.
Per farlo suppongo n=a*b , essendo a il minore fattore primo di n, e calcolo $ \binom{n-1}{a} $ mod n; noto che in questo coeff.binomiale, che si può riscrivere come $ \frac{(n-1)*(n-2)*\dots*(n-a)}{a*(a-1)*\dots*1} $, non ci sono fattori b e c'è un solo fattore a che si semplifica, dunque sono autorizzato a lavorare nel campo degli interi minori di n e coprimi con n (ignorando per ora il fattore (n-a) che era divisibile per a, al numeratore). In questa situazione vale ancora il calcolo di cui sopra (potrei rifarlo, ma concettualmente è davvero identico...), e darà quindi un risultato pari a 1 o -1; moltiplicando il tutto per $ \frac{n-a}{a} $ ottengo dunque un numero che non è compatibile con la relazione suddetta, che quindi risulta falsa. CVD

Spero sia sufficientemente chiaro...

Ciao ciao
Marino

[MindFlyer]

Scusa gip, ma penso che tu abbia tirato fuori un po' troppa roba avanzata come alcuni risultati di teoria dei gruppi, etc, per risolvere un problema banale (ricorda che siamo nel forum del problem solving olimpico, non in matematica avanzata, e certi discorsi sarebbe meglio non farli qui). Inoltre, la parte sui quadrati non mi convince fino in fondo...

Ecco come risolverei l'implicazione interessante del problema (se n è primo, allora vale la relazione):

Sappiamo che $ {n-1 \choose k} $ è un intero. Inoltre, nell'ipotesi che $ n $ sia primo, abbiamo che $ k! $ non è multiplo di $ n $. Allora, moltiplicando entrambi i membri dell'equazione per $ k! $ ricaviamo la forma equivalente

$ (n-1)(n-2)\ldots (n-k)\equiv (-1)^k \cdot k! (\bmod n) $.

Ma il membro a sinistra si può riscrivere come $ (-1)(-2)\ldots (-k)\equiv (-1)^k \cdot k! (\bmod n) $, e questo conclude la prova.

[HiTLeuLeR]

Il denominatore è dato dal prodotto tra i k elementi più piccoli e gli n-1-k elementi più piccoli, che è uguale (a meno del segno qualora $ \frac{n-1}{2} $ e k abbiano differente parità) al prodotto dei quadrati degli $ \frac{n-1}{2} $ elementi più piccoli

Temo che non ne verremo mai a capo... Tuttavia, dacché ci piace farci del male, non è detto che non ci si possa comunque provare!!! Dunque, gip... Ti spiace chiacchierarla meno e metterla in forma Matematica? Detta a quel modo, non è che si capisca granché... Ti andrebbe poi di dimostrarmi quella tua affermazione, qualunque cosa essa voglia dire?!? Per gentilezza, limitati al quote qui sopra, almeno per il momento... E soprattutto non divagare, te ne prego!!! Se possono esserti di aiuto, utilizza pure i seguenti fatti (di pubblico dominio):

Teorema #1 (di Wilson): essendo $ n\in\mathbb{N} $, risulta che è primo sse $ (n-1)!\equiv -1 \bmod n $.

Corollario #1: se $ n $ è un primo intero $ > 2 $, allora: $ \displaystyle{\left[\left(\frac{p-1}{2}}\right)!\right]^{\! 2} \equiv (-1)^{\frac{p+1}{2}} \bmod p $.

Se a qualcuno gira di dimostrare l'uno e l'altro, beh... tanto di guadagnato!!! Anche se forse i proof andrebbero spostati altrove, a quel punto lì... Vabbe', confidiamo nella saggezza dei moderatori, su!

[gip]

Uh oh... ok, chiedo doppiamente scusa, sia per l'inutile rozzezza nella dimostrazione, sia per aver nominato argomenti tabù... a questo riguardo, mi chiedo quale sia l'azione più appropriata nel caso in cui si voglia rispondere ad un problema "olimpico" adoperando (o citando) metodi più avanzati; ricopiare il problema nella sezione apposita e svolgerlo lì?

Grazie
Ciao ciao
Marino

useless-ps: Quanto ai quadrati, è stato un ragionamento nato contorto e tale rimasto: esempietto: p=13 e k=4: $ (1*2*3*4)*(1*2*3*4*5*6*7*8) = 1^{2}*2^{2}*3^{2}*4^{2}*5^{2}*6^{2} $, poiché $ 8\equiv-5(mod 13) $ e $ 7\equiv-6(mod 13) $ ; visto che la mia soluz. è stata stracciata in eleganza da quella di Mind e visto che non è questo il posto, passo e chiudo.

[HiTLeuLeR]

Ecco, quella di Mind è esattamente la dimostrazione cui avevo pensato anch'io per l'implicazione diretta del teorema. Non capisco tuttavia perché il nostro Flyer trovi che sia questa, e non l'altra, la condizione interessante del teorema... Boh, sarà una questione di gusti?!?

[MindFlyer]

Anche la seconda parte si può sbrogliare in modo più semplice (e soprattutto senza discorsi strani sui quadrati):

Definisco, come gip, $ n=a\cdot b $, dove $ a $ è il più piccolo divisore primo di $ n $, e pongo $ k=a $. Questa volta moltiplico tutto per $ (a-1)! $, che è coprimo con $ n $ (altrimenti $ a $ non sarebbe il minimo divisore primo di $ n $). Voglio dimostrare allora che

$ (n-1)(n-2)\ldots (n-a+1)\cdot \frac{n-a}{a} \neq (-1)^a \cdot (a-1)!(\bmod n) $.

Ma $ \frac{n-a}{a}=b-1 $, da cui

$ (-1)^{a-1}\cdot (a-1)! \cdot (b-1) \neq (-1)^a\cdot (a-1)! (\bmod n) $,

che si semplifica (sempre sfruttando il fatto che $ (a-1)! $ e $ n $ sono coprimi) e si riduce a $ b\neq 0 (\bmod n) $, che è vera perché $ 0<b<n $.

[HiTLeuLeR]

Ok, tentiamo in un altro modo, ho capito... Mio Dio, se solo gli uomini collaborassero di più!!!

Il denominatore è dato dal prodotto tra i k elementi più piccoli e gli n-1-k elementi più piccoli, che è uguale (a meno del segno qualora $ \frac{n-1}{2} $ e k abbiano differente parità) al prodotto dei quadrati degli $ \frac{n-1}{2} $ elementi più piccoli.

Sarebbe a dire: $ \displaystyle{k! \cdot (n-1-k)! \equiv (-1)^{\frac{(n-1)}{2} - k} \cdot\prod_{i=1}^{(n-1)/2} i^2}\bmod n $ ?!? Nota che il fattore $ (-1)^{\frac{(n-1)}{2} - k} $ vale $ 1 $ oppure $ -1 $ in funzione del fatto che $ \frac{n-1}{2} $ e $ k $ abbiano o meno la stessa parità... Ci ho preso?!? Ho inteso bene il tuo discorso? Se sì, possiamo ragionarci... SPERIAMO!!!

[gip]

Ci ho preso?!?

Sì.

[MindFlyer]

a questo riguardo, mi chiedo quale sia l'azione più appropriata nel caso in cui si voglia rispondere ad un problema "olimpico" adoperando (o citando) metodi più avanzati; ricopiare il problema nella sezione apposita e svolgerlo lì?

Sì, sarebbe la cosa più appropriata. Ma teniamo questa regola solo per i casi estremi, altrimenti diventiamo matti. Se nella dimostrazione facciamo un accenno marginale a qualche risultato non elementare, non muore nessuno. L'importante è che chiunque abbia un bagaglio olimpico standard riesca comunque a seguire la dimostrazione. Ma se la dimostrazione si basa sostanzialmente su risultati non elementari, il povero olimpionico liceale si ritrova tagliato fuori, e ciò non è bello.

[HiTLeuLeR]

Sia lode al Cielo!!! Adesso rimane da capire comunque tutto il resto...

Sarebbe a dire: $ \displaystyle{k! \cdot (n-1-k)! \equiv (-1)^{\frac{(n-1)}{2} - k} \cdot\prod_{i=1}^{(n-1)/2} i^2}\bmod n $ ?!?

Giusto per inciso, nota come questo tuo claim, sulla base del corollario #1 di cui ho riferito poco sopra, equivale a dire che, se $ n $ è un primo intero $ > 2 $: $ k! \cdot (n-1-k)! \equiv (-1)^{k+1} \bmod n $. Ok, adesso ti chiedo... Come lo dimostri?!? Pare che sia parte essenziale del tuo proof, per cui la domanda è più che giustificata...

[HiTLeuLeR]

In tutto il putiferio scatenato dalla soluzione (?!?) di gip, m'ero perso per strada il proof di Mind per la condizione sufficiente del teorema (generalizzato) di Gosper. Beh, a parte che metterci un "visto", cosa potrei fare?

[gip]

Sarebbe a dire: $ \displaystyle{k! \cdot (n-1-k)! \equiv (-1)^{\frac{(n-1)}{2} - k} \cdot\prod_{k=1}^{(n-1)/2} k^2}\bmod n $

Come lo dimostri?!?

Dunque, puntiamo alla chiarezza totale.
Per evitare di fare confusione usiamo k una sola volta e riscriviamo la formula come $ \displaystyle{k! \cdot (n-1-k)! \equiv (-1)^{\frac{(n-1)}{2} - k} \cdot\prod_{x=1}^{(n-1)/2} x^2}\bmod n $.
Abbiamo $ \displaystyle{(-1)^{\frac{(n-1)}{2} - k} \cdot\prod_{x=1}^{(n-1)/2} x^2 $ $ \displaystyle{\equiv (-1)^{\frac{(n-1)}{2} - k} \cdot \prod_{x=1}^{k} x^2 \cdot \prod_{x=k+1}^{(n-1)/2} x^2 \bmod n} $.

D'altronde $ \displaystyle{k! \cdot (n-1-k)! \equiv \prod_{x=1}^{k} x^2 \cdot \prod_{x=k+1}^{n-1-k} x \bmod n } $.
Poiché poi si ha che, per ogni t, $ \displaystyle{ k+t \equiv -(n-k-t) \bmod n} $, posso riscrivere l'ultima produttoria, moltiplicando a due a due i corrispondenti $ k+t $ e $ n-k-t $, come $ \displaystyle{(-1)^{\frac{(n-1)}{2} - k} \cdot \prod_{x=k+1}^{(n-1)/2} x^2} $ (il primo fattore e' giustificato dal fatto che il segno cambia ogni volta che moltiplico due di questi termini, essendo essi opposti; di tali prodotti ne vanno fatti quindi $ \displaystyle{ \frac{[(n-k-1) - (k+1) +1]}{2} = \frac{n-1}{2} - k } $ ).
Da questo la tesi.

[HiTLeuLeR]

Credimi, non è mia intenzione essere persecutorio, ma sant'Iddio... Tu ci metti proprio impegno, ovvìa!!!

[...] Riscriviamo la formula come $ \displaystyle{k! \cdot (n-1-k)! \equiv (-1)^{\frac{(n-1)}{2} - k} \cdot\prod_{x=1}^{(n-1)/2} x^2}\bmod n $.
Abbiamo $ \displaystyle{(-1)^{\frac{(n-1)}{2} - k} \cdot\prod_{x=1}^{(n-1)/2} x^2 $ $ \displaystyle{\equiv (-1)^{\frac{(n-1)}{2} - k} \cdot \prod_{x=1}^{k} x^2 \cdot \prod_{x=k+1}^{(n-1)/2} x^2 \bmod n} $.

Alt, alt, alt... Perdonami, ma tutto questo è vero per quali valori del parametro $ k = 0, 1, \ldots, n-1 $ ?!? Ok, non ti affannare, rispondo io! E' vero per ogni $ k\in\{1, 2, \ldots, (n-3)/2\} $, il che (volendo proprio essere diligenti)già ti imporrebbe di: i) suppore $ n \geq 5 $, ergo discutere separatamente il caso $ n = 3 $; ii) assumere $ k \leq (n-1)/2 $, quando invece - in linea di principio - k può essere un intero qualsiasi nell'intervallo $ [0, n-1] $; iii) esaminare in modo indipendente i casi singolari $ k = 0 $ e $ k = (n-1)/2 $. Ebbene, la ii) non ti dà grossi problemi, viste le proprietà di "simmetria" del coefficiente binomiale (in fondo, il problema è partito pur sempre da lì); e la i) ce la si leva dalle scatole con una verifica diretta, così come pure ci si frigge in padella, in quattro e quattr'otto, i casi $ k=0 $ e $ k = (n-1)/2 $ riferiti dalla iii). Uh, tutto questo per dirti cosa?!? Boooh, non saprei, fa' un po' tu...

D'altronde $ \displaystyle{k! \cdot (n-1-k)! \equiv \prod_{x=1}^{k} x^2 \cdot \prod_{x=k+1}^{n-1-k} x \bmod n } $.

Valgono le stesse considerazioni dette qualche rigo sopra. Ma adesso arriva il meglio...

Poiché poi si ha che, per ogni t: $ k+t \equiv n-k-t \bmod n $

Ennò, questa non riesco proprio a capirla! Scusa tanto, eh... Per ogni $ t\in\mathbb{Z} $: $ k+t \equiv n-k-t \bmod n $ sse: $ k+t \equiv 0 \bmod n $, e non mi pare che questo sia "identicamente vero"!!! Boh, sarà l'ora tarda, non so che dirti... Aspetterò con ansia la nuova alba, sperando che finalmente si riesca ad aver ragione di cotanto scempio!!!