binomiali e primi

Numeri interi, razionali, divisibilità, equazioni diofantee, ...
Rispondi
Simo_the_wolf
Moderatore
Messaggi: 1036
Iscritto il: 01 gen 1970, 01:00
Località: Pescara

binomiali e primi

Messaggio da Simo_the_wolf » 19 mag 2006, 13:35

Dimostrare che, per tutti i primi $ p\geq 5 $ vale:

$ \displaystyle p^5 \mid \binom {p^2}p - p $

Più in generale, potenziando la tesi di un TST italiano...

$ \displaystyle p^{2n+1}\mid \binom {p^n}p - p^{n-1} $

Avatar utente
frengo
Messaggi: 223
Iscritto il: 01 gen 1970, 01:00

Messaggio da frengo » 21 mag 2006, 09:57

parto direttamente dal caso generale:

$ \displaystyle p^{2n+1} \mid \binom{p^n}p - p^{n-1} $

lavoriamo sul secondo membro:

$ \displaystyle \binom{p^n}p - p^{n-1}=\frac{p^{n-1}(p^n-1)\ldots(p^n-p+1)}{(p-1)(p-2)\ldots 3\cdot 2\cdot 1}-p^{n-1}=p^{n-1} $$ \displaystyle \left(\frac{(p^n-1)(p^n-2)\ldots(p^n-p+1)}{(p-1)(p-2)\ldots 3\cdot 2\cdot 1}-1\right) $

quella parentesi noi sappiamo essere un intero (è uguale a $ \displaystyle \binom{p^n-1}{p-1}-1 $)

quindi possiamo semplificare: ci rimane da dimostrare solo

$ \displaystyle p^{n+2} \mid \left(\frac{(p^n-1)(p^n-2)\ldots(p^n-p+1)}{(p-1)(p-2)\ldots 3\cdot 2\cdot 1}-1\right) $

e adesso impostiamo la congruenza

$ \displaystyle \left(\frac{(p^n-1)(p^n-2)\ldots(p^n-p+1)}{(p-1)(p-2)\ldots 3\cdot 2\cdot 1}-1\right) \equiv $ $ x \mod p^{n+2} $

$ {(p^n-1)(p^n-2)\ldots(p^n-p+1)-(p-1)!\equiv $ $ (p-1)!x \mod p^{n+2} $

e adesso svolgiamo il prodotto

$ {p^{2n}(\text{molte cose di cui non ci interessa})-p^n\left(\sum\limits_{i=1}^{p-1}\frac{(p-1)!}{i}\right) $ $ +(p-1)!-(p-1)!\equiv $ $ (p-1)!x \mod p^{n+2} $

quindi il membro di destra è divisibile per $ p^n $ e quindi lo è anche x, $ (p-1)!x=p^ny $ e ora ci rimane solo dadimostrare che $ y $ è divisibile per $ p^2 $.

$ \displaystyle \sum\limits_{i=1}^{p-1}\frac{(p-1)!}{i}\equiv $ $ y \mod p^2 $

$ \displaystyle \sum\limits_{i=1}^{\frac{p-1}{2}}\frac{(p-1)!}{i}+\frac{(p-1)!}{p-i}\equiv $ $ y \mod p^2 $

$ \displaystyle \sum\limits_{i=1}^{\frac{p-1}{2}}\frac{p(p-1)!}{i(p-i)}\equiv $ $ y \mod p^2 $

$ \displaystyle p\sum\limits_{i=1}^{\frac{p-1}{2}}\frac{(p-1)!}{i(p-i)}\equiv $ $ y \mod p^2 $

quindi ponndo y=pz

$ \displaystyle \sum\limits_{i=1}^{\frac{p-1}{2}}\frac{(p-1)!}{i(p-i)}\equiv $ $ z \mod p $

$ \displaystyle \sum\limits_{i=1}^{\frac{p-1}{2}}\frac{(p-1)!}{i^2)}\equiv $ $ -z \mod p $

$ \displaystyle \sum\limits_{i=1}^{\frac{p-1}{2}}\frac1{i^2}\equiv $ $ z \mod p $

i quadrati dei primi $ \frac{p-1}{2} $ numeri rappresentano tutti e soli i residui quadratici modulo p presi una volta sola.Devo ora dividere due casi:

1)$ p\equiv 3\mod4 \longrightarrow $ i residui quadratici sono un numero dispari, tra questi c'è 1 e non c'è -1.

In questo caso è possibile raggruppare tutti i residui quadratici a coppie di inversi, escludendo 1 che è inverso di se stesso(questo andrebbe dimostrato,ma forse lo posso dare per noto).risulta quindi:

$ \displaystyle \sum\limits_{i=1}^{\frac{p-1}{2}}\frac1{i^2}\equiv\sum\limits_{i=1}^{\frac{p-1}{2}}i^2\equiv\frac{\left(\frac{p-1}{2}\right)\left(\frac{p+1}{2}\right)p}{6}\equiv $ $ 0 \mod p $

e quindi abbiamo finito.

2)$ p\equiv 1\mod4 \longrightarrow $ i residui quadratici sono un numero pari, tra questi c'è sia 1 che -1.

In questo caso è possibile raggruppare tutti i residui quadratici a coppie di inversi, escludendo 1 e -1 che sono inversi di se stessi.risulta quindi allo stesso modo:

$ \displaystyle \sum\limits_{i=1}^{\frac{p-1}{2}}\frac1{i^2}\equiv\sum\limits_{i=1}^{\frac{p-1}{2}}i^2\equiv\frac{\left(\frac{p-1}{2}\right)\left(\frac{p+1}{2}\right)p}{6}\equiv $ $ 0 \mod p $.

e quindi abbiamo finito, stavolta del tutto.(...puff)

ciao ciao

ps volevo cercare di nasconderla, ma data la quantità di formule è quasi inutile...basterà la lunghezza della soluzione a scoraggiare i più...

darkcrystal
Messaggi: 696
Iscritto il: 14 set 2005, 11:39
Località: Chiavari

Messaggio da darkcrystal » 21 mag 2006, 11:09

Scusa frengo mi sfugge un passaggio (che è poi quello su cui mi ero bloccato :oops: nella mia dimostrazione)
frengo ha scritto: $ \displaystyle \sum\limits_{i=1}^{\frac{p-1}{2}}\frac1{i^2}\equiv\sum\limits_{i=1}^{\frac{p-1}{2}}i^2 $...
Cosa ci fa dire che la somma degli inversi dei residui quadratici è congrua alla somma dei residui? Che sia vero, ok... ma è un fatto noto o va dimostrato... ?
Insomma, mi affido a te per una spiegazione, sempre che tu non sia già in viaggio per il PreIMO. Grazie!

Ciao!
"Solo due cose sono infinite: l'universo e la stupidità dell'uomo, e non sono tanto sicuro della prima" - Einstein

Membro dell'EATO

ReKaio
Messaggi: 565
Iscritto il: 01 gen 1970, 01:00
Località: Terra degli Shura (pisa)
Contatta:

Messaggio da ReKaio » 21 mag 2006, 11:56

l'inverso di un quadrato e' sempre un quadrato, quindi ti limiti a permutarli nella somma

(bella dimostrazione, finisco di leggerla)
_k_

Avatar utente
frengo
Messaggi: 223
Iscritto il: 01 gen 1970, 01:00

Messaggio da frengo » 21 mag 2006, 12:38

riscrivo l'ultimo passaggio, a partire da quando divido i due casi (che ora non farò più)

allora:

$ \displaystyle \sum\limits_{i=1}^{\frac{p-1}{2}}\left(\frac{1}{i}\right)^2 $

dato che l'insieme di tutti gli i^2 della sommatoria contiene tutti i residui quadratici presi una volta sola, l'insieme di tutti gli (1/i)^2 contiene elementi:

-tutti distinti
-tutti quadrati

quindi i due insiemi coincidono, e quindi

$ \displaystyle \sum\limits_{i=1}^{\frac{p-1}{2}}\left(\frac{1}{i}\right)^2=\sum\limits_{i=1}^{\frac{p-1}{2}}i^2 $

forse adesso è più chiaro

ciao ciao

Rispondi