-1, 2 o -2 sono quadrati modulo p

Numeri interi, razionali, divisibilità, equazioni diofantee, ...
Rispondi
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...

-1, 2 o -2 sono quadrati modulo p

Messaggio da pic88 » 27 nov 2007, 17:27

Viste le mia scarse abilità in TdN, avrei bisogno di sapere se la dimostrazione di questo fatto è elementare, e magari avere un suggerimento... :roll:

ah, p è un primo qualsiasi.

Avatar utente
FeddyStra
Messaggi: 403
Iscritto il: 19 set 2006, 15:34
Località: 45° 7' 19.2'' N 7° 23' 20.1'' E

Messaggio da FeddyStra » 27 nov 2007, 19:24

Non sono banalissime, ma se ti guardi un po' il criterio di Gauss sono fattibili.
In particolare la più semplice è quella riguardante -1.
[quote="julio14"]Ci sono casi in cui "si deduce" si può sostituire con "è un'induzione che saprebbe fare anche un macaco", ma per come hai impostato i conti non mi sembra la tua situazione...[/quote][quote="Tibor Gallai"]Ah, un ultimo consiglio che risolve qualsiasi dubbio: ragiona. Le cose non funzionano perché lo dico io o Cauchy o Dio, ma perché hanno senso.[/quote]To understand recursion, you fist need to understand recursion.
[tex]i \in \| al \| \, \pi \, \zeta(1)[/tex]

Avatar utente
pi_greco_quadro
Messaggi: 158
Iscritto il: 01 gen 1970, 01:00
Località: Verona

da patavino a patavino

Messaggio da pi_greco_quadro » 27 nov 2007, 22:05

dunque.. lasciamo il caso $ p=2 $ per il quale la tesi è ovviamente vera.

Innanzitutto sappiamo che, se $ p=4k+3 $, allora $ u^2\not\equiv -1 \pmod p $, infatti se per assurdo valesse il contrario, avremmo che, elevando ambo i lati alla $ \frac{p-1}{2} $ che è dispari, otterremo $ u^{p-1} \equiv -1 \pmod p $, che è ovviamente impossibile per il piccolo teorema di fermat e considerato che, per $ p>2 $, $ 1\not\equiv -1 \pmod p $.

Ora diamo qui un piccolo fatto per noto, ovvero l'esistenza di un generatore per un modulo primo qualsiasi. Sia $ g $ il generatore in questione.

Sia $ p=4k+1 $

Ora, sappiamo che $ g^{p-1} \equiv 1\pmod p $ ma, per $ m<p-1=ord_p(g) $, $ g^m\not\equiv 1 \pmod p $

Dunque, se consideriamo $ g^{\frac{p-1}{2}} $, ne segue che $ g^{\frac{p-1}{2}}\equiv -1 \pmod p $, dunque di sicuro esiste il nostro $ u^2\equiv -1 \pmod p $ se $ p=4k+1 $.

Mostriamo ora che, se $ p=4k+3 $, allora esiste $ u^2\equiv 2\;, -2 \pmod p $

Consideriamo ancora una volta un generatore $ g $. Supponiamo per assurdo che sia $ g^{\alpha} \equiv 2 \pmod p $ e $ g^{\beta} \equiv -2 \pmod p $, con $ \alpha, \beta $ entrambi dispari. Se così non fosse avremmo infatti concluso.

Ovviamente il passaggio sopra è autorizzato considerato che $ g $ è un generatore e $ 2\not\equiv -2 \pmod p $

Ma, allora, considero $ g^{\alpha}+g^{\beta} \equiv g^{\alpha}(1+g^{\beta-\alpha}) \equiv 0\pmod p $ da cui, essendo $ g\not\equiv 0\pmod p $, ne segue $ g^{\beta-\alpha}\equiv -1 \pmod p $.

Questo è tuttavia un assurdo, in quanto $ \alpha-\beta $ è pari ed abbiamo dimostrato sopra che la congruenza $ l^2\equiv - 1 \pmod p $ non ha soluzioni per $ p=4k+3 $. Dunque almeno uno tra $ \alpha\;, \beta $ è pari, e questo conclude la dimostrazione.
Disco es cultura, metal es religion (Metal py)
"Ti credevo uno stortone.. e pure vecchio.. (Lei)"

Rispondi