Numero residui...

[moebius]

Quanti sono al variare di $ \displaystyle x $ in $ \displaystyle \left[0, \ldots, p-1\right] $ i residui quadratici modulo $ \displaystyle p $ dati da $ \displayatyle x^3 - x $ se $ \displaystyle p \equiv 3 \ \left(mod \ 4\right) $?

Edit: Riformulato due post più sotto in modo quasi equivalente...

[gianmaria]

i residui quadratici modulo $ \displaystyle p $

Cosa significa? Con un testo più chiaro, forse avresti già avuto una risposta.

[moebius]

Proviamo a riformulare:
Sia $ \displaystyle p \in \mathfrak{P} $ t.c. $ \displaystyle p \equiv 3 \ \left(mod \ 4\right) $.
Quante sono le coppie $ \displaystyle \left(x, y\right)\in \left[0, \ldots, p-1\right] \times \left[0, \ldots, p-1\right] $ che sono soluzione dell'equazione congruenziale:
$ \displaystye y^2 \equiv x^3 - x \ \left(mod \ p\right) $
Così è + chiaro? (Secondo me la formulazione precedente era di aiuto, fate vobis...)

Edit: corretto, thx fph

[fph]

@gianmaria: (supponendo che tu sappia già le congruenze), un residuo quadratico modulo $ p $ è un intero che è congruo a un quadrato modulo $ p $.
Ad esempio, i residui quadratici modulo $ 5 $ sono tutti i numeri congrui a $ 0,1,4 $, perché esistono quadrati congrui a $ 0,1,4 $ modulo $ 5 $ ma non ne esistono che siano congrui a $ 2 $ o a $ 3 $. (prova a verificarlo...)

Ti può tornare utile sapere che i residui quadratici modulo $ p $ scelti in $ (0,1,\ldots p-1) $ sono sempre $ \frac{p+1}{2} $, tranne che per $ p=2 $ (cioè, sono "metà più una delle classi di resto").

@moebius: a parte HitlEuler che ha un gusto particolare per l'eccessiva formalizzazione, per tutto il resto del mondo è molto più chiara la prima versione. In particolare quella P storta per indicare i primi la usa praticamente solo lui.

@moebius: occhio, nella seconda versione del testo hai scritto $ p \equiv 0 \mod 3 $ invece che $ p \equiv 3 \mod 4 $

ciao a tutti,

[HiTLeuLeR]

@moebius: a parte HitlEuler [...] quella P storta per indicare i primi la usa praticamente solo lui.

Ma com'è che mi si tira sempre in ballo?! Firmus in fide Dei, finirò per credere che si riponga in me una stima in vero immeritata... In ogni caso, lasciati dire, fph, che per una volta almeno ti sbagli in modo grossolano: prova a cercare con maggiore attenzione fra i volumi della certamente ricca biblioteca di mamma Normale!

OT: posso dare un hint sul problema di moebius, vero? Dunque dico $ (p-3)/2 $, giusto per rimanere in tema e non allargarsi su discorsi che hanno tanto un sapore d'infantile...

[HiTLeuLeR]

Sia $ n $ il numero degl interi nell'insieme $ \{0,1, \ldots, p-1\} $ tali che $ x^3 - x $ sia un residuo quadratico $ \bmod\;\! p $. Se $ x = 0 $, $ x = 1 $ oppure $ x = p-1 $, allora $ x^3-x \equiv x(x-1)(x+1) \equiv 0 \bmod p $, e l'equazione $ u^2 \equiv 0 \bmod p $ è certo risolvibile in interi. Sia dunque per il seguito $ 2 \leq x \leq p-2 $, con $ p > 3 $. Allora $ \gcd(x^3-x,p) = 1 $ e perciò $ \displaystyle\left\lgroup\frac{x^3-x}{p}\right\rgroup\!\! = \pm 1 $. Senonché (in base alle proprietà elementari del simbolo di Legendre):

$ \displaystyle\left\lgroup\frac{x^3-x}{p}\right\rgroup\!\! = \pm 1\quad\Longrightarrow\quad\displaystyle\left\lgroup\frac{(p-x)^3-(p-x)}{p}\right\rgroup\!\! = $ $ \displaystyle (-1)^{\frac{p-1}{2}}\cdot \left\lgroup\frac{x^3-x}{p}\right\rgroup\!\! = \pm 1 \cdot (-1)^{\frac{p-1}{2}} $

Dunque $ \displaystyle\left\lgroup\frac{x^3-x}{p}\right\rgroup\!\! = \pm 1 $ sse $ \displaystyle\left\lgroup\frac{(p-x)^3-(p-x)}{p}\right\rgroup\!\! = \mp\;\! 1 $, quando $ p \equiv 3 \bmod 4 $. Ne viene che, nelle ipotesi del problema, il numero $ v $ dei residui quadratici $ \bmod\;\! p $ nell'insieme $ \{2, 3, \ldots, p-2\} $ eguaglia il numero $ v^* $ dei non-residui. Pertanto $ 2v = p-3 $, e finalmente $ n = v+ 3 = (p+3)/2 $.

[moebius]

Tutto giusto, tranne un segno alla fine. Se qualcuno ha voglia, per completezza, può provare a fornire una risposta alla seconda formulazione, che differisce un poco dalla prima ma che è una sua conseguenza diretta.

@Hit: Una questione tipografica: usare \lgroup e \rgroup per il simbolo di Legendre è una tua scelta personale o una convenzione?

Bonus question (ancora non risolta, quindi potrebbe essere fuori dagli argomenti di questa sezione): rispondere alla seconda (o alla prima) formulazione se $ p \equiv 1 \ \left(mod \ 4\right) $

[HiTLeuLeR]

Tutto giusto, tranne un segno alla fine.

Ma quale segno, scusa?!

@Hit: Una questione tipografica: usare \lgroup e \rgroup per il simbolo di Legendre è una tua scelta personale o una convenzione?

Boh, in questo seguo Michele Cipolla, di cui (certo indegnamente!) mi vo' professando discipulus.

Bonus question (ancora non risolta, quindi potrebbe essere fuori dagli argomenti di questa sezione): rispondere alla seconda (o alla prima) formulazione se $ p \equiv 1 \bmod 4 $

Temo non si possa dire nulla di analogo al caso precedente. Ho fatto qualche prova con il Mathematica e la distribuzione dei residui/non residui sembra davvero troppo selvaggia. Ma poi chi può dirlo...

[moebius]

Ehm, ho letto male
Però rileggendo non ho capito cosa è n...

[HiTLeuLeR]

Sia $ n $ il numero degl interi nell'insieme $ \{0,1, \ldots, p-1\} $ tali che $ x^3 - x $ sia un residuo quadratico $ \bmod\;\! p $.

E' la risposta alla tua domanda, moebius...

[moebius]

LOL...
Sisi, è che rileggendo solo l'ultima parte mi ero perso la prima
Tutto giusto

[HiTLeuLeR]

Sia $ \displaystyle p \in \mathfrak{P} $ t.c. $ \displaystyle p \equiv 3 \ \left(mod \ 4\right) $. Quante sono le coppie $ \displaystyle \left(x, y\right)\in \left[0, \ldots, p-1\right] \times \left[0, \ldots, p-1\right] $ che sono soluzione dell'equazione congruenziale: $ \displaystye y^2 \equiv x^3 - x \bmod p $ ?

Siano $ a \in \mathbb{Z} $ un residuo quadratico $ \bmod\;\! p $; $ y_1, y_2 \in \mathcal{D}_p $, con $ \mathcal{D}_p = \{0, 1,\ldots, p-1\} $, tali che $ y_1^2 \equiv y_2^2 \equiv a\bmod p $ ed $ y_1 < y_2 $. Allora $ p \mid (y_1 - y_2) $ oppure $ p \mid (y_1 + y_2) $. Eppure $ 0 < | y_1 - y_2 | < p $, per cui a forza $ p \mid (y_1 + y_2) $, ovvero $ y_1 + y_2 = p $.

Ne discende che, se $ a $ è residuo quadratico $ \bmod\;\! p $ e $ p $ è dispari, allora è univocamente determinata una coppia $ (y_1, y_2)\in\mathcal{D}_p\times \mathcal{D}_p $ tale che $ y_1^2 \equiv y_2^2 \equiv a \bmod p $, ché se esistessero (a due a due distinti) $ y_1, y_2, y_3 \in \mathcal{D}_p $ tali che $ y_1^2 \equiv y_2^2 \equiv y_3^2 \equiv a \bmod p $, allora si avrebbe $ y_1 + y_2 = y_1 + y_3 = y_2 + y_3 $, assurdo! Ogni conclusione è a dir poco triviale (se non persino volgare), a questo punto...