Dimostrazione residui quadratici

[flutist001]

Salve a tutti, sto setacciando Internet ma senza successo per la dimostrazione di questo fatto : i residui quadratici modulo un primo $p$ compresi tra $1$ e $p-1$ sono esattamente $\frac{p-1}{2}$ .
Sapreste aiutarmi? Grazie infinite

[EvaristeG]

Beh, io non ti scrivo la dimostrazione, ma ti do un aiutino su come farla: i residui quadratici sono i resti della divisione per $p$ dei quadrati, prendi due numeri $1\leq a,b\leq p-1$ che siano entrambi residui quadratici, ovvero $a\equiv x^2$ e $b\equiv y^2$ $\bmod p$ per due interi $1\leq x,y\leq p-1$. Ora supponi che $a=b$. Questo cosa ti dice su $x,y$? A questo punto, non c'è qualche fattorizzazione furba che puoi fare?

[flutist001]

i residui quadratici sono i resti della divisione per $p$ dei quadrati

Evidentemente non ho nemmeno capito cosa effettivamente sia un residuo quadratico . La tua definizione non implica che un residuo è sempre compreso tra $1$ e $p-1$ ? Perché se è così allora ho capito la dimostrazione che fa il mio libro, ma io credevo che un residuo fosse un qualunque numero naturale $a$ tale che $a \equiv x^2 \pmod{p}$...

[Gi.]

$ a $ è un residuo quadratico modulo $ p $ se e solo se esiste un $ x $ tale che

$ x^2 \equiv a \pmod p $

Sotto spoiler metto una roba un po' casereccia per contarli:

Testo nascosto:

Proviamo prima due casi facili da controllare: mod 5 e mod 7.

$ 0 \longrightarrow 0 \equiv 0 \pmod p $
$ 1 \longrightarrow 1 \equiv 1 \pmod p $
$ 2 \longrightarrow 4 \equiv 4 \pmod p $
$ 3 \longrightarrow 9 \equiv 4 \pmod p $
$ 4 \longrightarrow 16 \equiv 1 \pmod p $


$ 0 \longrightarrow 0 \equiv 0 \pmod p $
$ 1 \longrightarrow 1 \equiv 1 \pmod p $
$ 2 \longrightarrow 4 \equiv 4 \pmod p $
$ 3 \longrightarrow 9 \equiv 2 \pmod p $
$ 4 \longrightarrow 16 \equiv 2 \pmod p $
$ 5 \longrightarrow 25 \equiv 4 \pmod p $
$ 6 \longrightarrow 36 \equiv 1 \pmod p $

Penso tu possa notare una certa simmetria, cioè ogni residuo quadratico, escluso lo 0, si ripete esattamente due volte.
Dimostrato questo seguirebbe immediatamente che essi sono $ \displaystyle \frac{p-1}{2} $, dacchè tutti i residui sono $ p $ e dobbiamo togliere lo 0.

Cerchiamo di capire in generale perché vale quanto detto: dato il residuo $ k $ ci sarà anche quello che puoi esprimere nella forma $ k-p $ [ad esempio, in quello di sopra, abbiamo $ 2 $ ma anche $ 7 $ che è $ \equiv 5-7=-2 \pmod 7 $], quest'ultimo ridotto mod $ p $ sarà equivalente a $ -k $ che elevato al quadrato è $ k^2 $, proprio come $ k $. Quindi i residui si presentano a coppie, 0 escluso, e sono $ \displaystyle \frac{p-1}{2} $.

Adesso però tu potresti muovermi un'obiezione: potrebbero esistere $ x^2 \equiv y^2 \pmod p $ con $ y \not =p-x $ e $ y \not = x $ $ \pmod p $.
Qui entra in gioco il suggerimento di EvaristeG, infatti $ x^2 -y^2 \equiv 0 \pmod p \longrightarrow (x-y)(x+y) \equiv 0 \pmod p \Rightarrow x \equiv \pm y \pmod p $,ma $ x $ e $ y $ sono residui quindi sono minori di $ p $ e conseguentemente $ x= \pm y $, e siamo proprio nei casi esclusi.
Questo conclude la dimostrazione.

La tua definizione non implica che un residuo è sempre compreso tra $ 1 $ e $ p−1 $ ?

Beh, se il residuo fosse maggiore di $ p $ allora si potrebbe ridurlo modulo $ p $ e farlo diventare minore di $ p $.

[flutist001]

Perdonate la cocciutaggine xD forse se scrivo esattamente il mio dubbio sarà più chiaro, allora: il mio libro dice "i residui quadratici di $p$ sono congrui a $1^2, 2^2,...,(p-1)^2$, ma questi sono congruenti a coppie, perché $$x^2 \equiv (p-x)^2 \mod{p}$$ in quanto ...(lo dimostra)...quindi una metà dei numeri $1,2,...p-1$ sono residui e l'altra sono non residui, e mi è chiaro il perché ci siano almeno $(p-1)/2$ residui, ma come si fa a sapere che gli altri non sono congruenti modulo $p$ ad un quadrato maggiore di $(p-1)^2$ ?

[Gi.]

Non so se ho ben capito quel che intendi, ma

$ x^2\equiv p+k \pmod p $, con $ 1 \le k \le p-1 $, allora $ x^2 \equiv k $ ridotto modulo $ p $, e $ 1 \le k \le p-1 $.

Secondo me ti stai ponendo nel modo sbagliato nei confronti della definizione: un residuo quadratico è un numero $ a $ che viene generato da un quadrato quanto ridotto modulo $ p $. Detto bruttalmente: prendi i residui moduli $ p $ (che sono $ p-1 $), li elevi al quadrato, scarti i doppioni e quelli che ti rimangono sono tutti i residui quadrati, quindi un qualsiasi quadrato sarà congruo ad uno di quei numeri modulo $ p $.