Simbolo di Legendre

Cosa sono il pigeonhole e l'induzione? Cosa dice il teorema di Ceva? 1 è un numero primo?
Rispondi
ngshya
Messaggi: 231
Iscritto il: 26 gen 2010, 19:08
Contatta:

Simbolo di Legendre

Messaggio da ngshya » 16 giu 2010, 18:28

Guardando la soluzione dell'esercizio PreIMO-N6, che è fra gli esercizi di ammissione per il Senior (mi sembra di aver capito che è lecito chiedere ulteriori chiarimenti sui passaggi non capiti o capiti poco, no :?: ), è saltato fuori un piccolo lemma che non riesco a dimostrare.
Sia $ $p$ $ un numero primo dispari, allora esiste $ $x$ $ intero tale che $ $x^2\equiv 2 \pmod p$ $ se e solo se $ $p \equiv \pm 1 \pmod 8$ $.
Una piccola ricerca su internet e ho scoperto che è una delle proprietà del Simbolo di Legendre (http://en.wikipedia.org/wiki/Legendre_symbol).

Qualcuno è così pio da illuminarmi con una dimostrazione, o, meglio ancora, con qualche hint?

pic88
Messaggi: 741
Iscritto il: 16 apr 2006, 11:34
Località: La terra, il cui produr di rose, le dié piacevol nome in greche voci...

Messaggio da pic88 » 16 giu 2010, 20:24

La dimostrazione piu' breve che conosco usa questo.

ngshya
Messaggi: 231
Iscritto il: 26 gen 2010, 19:08
Contatta:

Messaggio da ngshya » 17 giu 2010, 13:35

Grazie pic88, adesso leggo tutto. :wink:

Avatar utente
kn
Messaggi: 508
Iscritto il: 23 lug 2007, 22:28
Località: Sestri Levante (Genova)
Contatta:

Messaggio da kn » 18 giu 2010, 11:32

Per il 2 ce n'è una più breve ed elegante:

Sia $ \displaystyle~s=\frac{p-1}{2} $. Scriviamo queste equazioni:

$ \displaystyle~1 = (-1)(-1)^1 $
$ \displaystyle~2 = 2(-1)^2 $
$ \displaystyle~3 = (-3)(-1)^3 $
$ \displaystyle~4 = 4(-1)^4 $
e così via fino a s.

Moltiplichiamo tutte queste equazioni.
Il primo membro dell'equazione ottenuta è s!
Il secondo membro è $ \displaystyle~[(-1)2(-3)4\cdots((-1)^s s)](-1)^{1+2+\ldots+s} $
I negativi possiamo considerarli come dei numeri pari $ \displaystyle~\pmod p $:
$ \displaystyle~RHS\equiv [(p-1)2(p-3)4\cdots](-1)^{1+2+\ldots+s} $$ \displaystyle~\equiv [(2\cdot s)(2\cdot 1)(2\cdot(s-1))(2\cdot 2)\cdots](-1)^{1+2+\ldots+s} $
Poiché tra le parentesi quadre ci sono ancora s termini, $ \displaystyle~RHS\equiv 2^s s!(-1)^{1+2+\ldots+s}\equiv\left(\frac{2}{p}\right)s!(-1)^{\frac{s(s+1)}{2}} $
quindi (da $ \displaystyle~LHS=s!=RHS $) $ \displaystyle~1\equiv \left(\frac{2}{p}\right)(-1)^{\frac{s(s+1)}{2}}\pmod p $, ma, dato che il secondo membro è $ \displaystyle~\pm 1 $, deve valere l'uguaglianza $ \displaystyle~1=\left(\frac{2}{p}\right)(-1)^{\frac{s(s+1)}{2}} $ o anche $ \displaystyle~\left(\frac{2}{p}\right)=(-1)^{\frac{s(s+1)}{2}}=(-1)^\frac{p^2-1}{4} $
Viviamo intorno a un mare come rane intorno a uno stagno. (Socrate)

ngshya
Messaggi: 231
Iscritto il: 26 gen 2010, 19:08
Contatta:

Messaggio da ngshya » 20 giu 2010, 20:44

kn ha scritto:Per il 2 ce n'è una più breve ed elegante
:D Grazie!

ngshya
Messaggi: 231
Iscritto il: 26 gen 2010, 19:08
Contatta:

Messaggio da ngshya » 20 giu 2010, 21:14

kn ha scritto:... o anche $ \displaystyle~\left(\frac{2}{p}\right)=(-1)^{\frac{s(s+1)}{2}}=(-1)^\frac{p^2-1}{4} $
Solo una cosa, non dovrebbe essere $ $\frac{p^2-1}{8}$ $ all'esponente?

Rispondi