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
Dimostrazione residui quadratici
-
- Messaggi: 35
- Iscritto il: 12 feb 2012, 20:08
Dimostrazione residui quadratici
Ultima modifica di flutist001 il 02 feb 2014, 09:40, modificato 1 volta in totale.
Re: Dimostrazione residui quadratici
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?
-
- Messaggi: 35
- Iscritto il: 12 feb 2012, 20:08
Re: Dimostrazione residui quadratici
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}$...EvaristeG ha scritto: i residui quadratici sono i resti della divisione per $p$ dei quadrati
Re: Dimostrazione residui quadratici
$ 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:
$ x^2 \equiv a \pmod p $
Sotto spoiler metto una roba un po' casereccia per contarli:
Testo nascosto:
Beh, se il residuo fosse maggiore di $ p $ allora si potrebbe ridurlo modulo $ p $ e farlo diventare minore di $ p $.flutist001 ha scritto:La tua definizione non implica che un residuo è sempre compreso tra $ 1 $ e $ p−1 $ ?
Ultima modifica di Gi. il 02 feb 2014, 14:02, modificato 1 volta in totale.
-
- Messaggi: 35
- Iscritto il: 12 feb 2012, 20:08
Re: Dimostrazione residui quadratici
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$ ?
Re: Dimostrazione residui quadratici
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 $.
$ 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 $.