Home

Federica EU

1/12

Maria De Falco » 12.Resti quadratici e simbolo di Legendre

Definizione del simbolo di Legendre

Definizione 12.1

Sia p un numero primo dispari, e sia [a]_p un elemento di Z_p*.
Si dice che a è un resto quadratico modulo p se [a]_p è un quadrato in Z_p*.
Si dice che a è un non-resto quadratico modulo p se [a]_p non è un quadrato in Z_p*.

Definizione 12.2
Sia p un numero primo dispari, e sia a un numero intero.
Il simbolo di Legendre $\left(\frac{a}{p}\right)$ è definito come segue:
$\left(\frac{a}{p}\right)$ =0 se p divide a
$\left(\frac{a}{p}\right)$ =1 se a è un resto quadratico modulo p
$\left(\frac{a}{p}\right)$ =-1 se a è un non-resto quadratico modulo p

Prime proprietà del simbolo di Legendre

Proposizione 12.3

Sia p un numero primo dispari. Allora per ogni numero intero a,

$\left(\frac{a}{p}\right)\equiv a^{\frac{p-1}{2}}$ (mod p)

Dimostrazione
Se a è un multiplo di p, allora $\left(\frac{a}{p}\right)=0\equiv a^{\frac{p-1}{2}}$ (mod p).
Si supponga ora che a non sia un multiplo di p
⇒ [a]_p appartiene a Z_p* ⇒ $\left([a]_p^{\frac{p-1}{2}}\right)^2$ =[a]_p^p-1=[1]_p.
D’altra parte Z_p* è ciclico ⇒ [-1]_p è l’unico elemento di periodo 2 di Z_p* ⇒ $[a]_p^{\frac{p-1}{2}}$ è uguale a [1]_p oppure a [-1]_p , cioè
$a^{\frac{p-1}{2}}$ ≡1 (mod p) oppure $a^{\frac{p-1}{2}}$ ≡-1 (mod p).

Prime proprietà del simbolo di Legendre

Sia ora [g]_p un generatore di Z_p* , e sia n un numero intero tale che [a]_p=[g]_pⁿ .
D’altra parte
$\left(\frac{a}{p}\right)$ =1 ⇒ [a]_p è un quadrato in Z_p*⇔ né pari⇒ $n\frac{p-1}{2}$ è un multiplo di p-1⇔ $[a]_p^{\frac{p-1}{2}}=[g]_p^{n\frac{p-1}{2}}$ =[1]_p⇔ $a^{\frac{p-1}{2}}$ ≡1 (mod p)
Dunque $\left(\frac{a}{p}\right)\equiv a^{\frac{p-1}{2}}$ (mod p).
Dalla proposizione precedente e dal fatto che 1 e -1 sono incongrui modulo p, segue il prossimo corollario:

Corollario 12.4
Sia p un numero primo dispari. Allora
$\left(\frac{1}{p}\right)$ =1 e $\left(\frac{-1}{p}\right)=(-1)^{\frac{p-1}{2}}$

Prime proprietà del simbolo di Legendre

Proposizione 12.5

Sia p un numero primo dispari. Allora per ogni numero intero a,

$\left(\frac{ab}{p}\right)=\left(\frac{a}{p}\right)\left(\frac{b}{p}\right)$

Dimostrazione

$\left(\frac{ab}{p}\right) \equiv (ab)^{\frac{p-1}{2}}=a^{\frac{p-1}{2}}b^{\frac{p-1}{2}} \equiv \left(\frac{a}{p}\right)\left(\frac{b}{p}\right)\; (mod \; p)$
⇒ $\left(\frac{ab}{p}\right)=\left(\frac{a}{p}\right)\left(\frac{b}{p}\right)$

(perché 0,1 e -1 sono a due a due incongrui modulo p).

Prime proprietà del simbolo di Legendre

Lemma 12.6

Sia n un numero naturale dispari. Allora n²-1 è un multiplo di 8.

Dimostrazione

Esiste un numero k appartenente a N₀ tale che n=2k+1 ⇒ n²-1=(2k+1)²-1=4k²+4k=4k(k+1), che è un multiplo di 8 perché uno fra i due numeri k e k+1 è pari.

Proposizione 12.7

Sia p un numero primo dispari. Allora
$\left(\frac{2}{p}\right)=(-1)^{\frac{p^2-1}{8}}$

Dimostrazione

Si ponga per ogni n appartenente a N₀ ,
f(n)=0 se n è pari; f(n)= $(-1)^{\frac{n^2-1}{8}}$ se n è dispari.
E’ facile verificare che per ogni m,n appartenenti a N₀ ,si ha f(mn)=f(m)f(n).

Prime proprietà del simbolo di Legendre

Sia F un campo di ordine p², e sia b un elemento di periodo 8 di F* (quindi b⁴=-1).

Si ponga ora
$G=\sum_{j=0,\dots ,7}f(j) b ^j$
si calcolerà in due modi diversi G^p.

Primo Modo
$G^p=\left(G^2\right)^{\frac{p-1}{2}}G$ ;
$G^2=\left(\sum_{j=0,\dots ,7}f(j) b ^j\right)^2=(b-b^3-b^5+b^7)^2=(2(b-b^3))^2=4(b^2-2b^4+b^6)=8$
$\Rightarrow\; G^p=\left(G^2\right)^{\frac{p-1}{2}}G=8^{\frac{p-1}{2}}G=\left(\frac{8}{p}\right)G=\left(\frac{2}{p}\right)^3G=\left(\frac{2}{p}\right)G$

Prime proprietà del simbolo di Legendre

Secondo Modo

$G^p=\left(\sum_{j=0,\dots ,7}(f(j) b ^j)^p\right)=\sum_{j=0,\dots ,7}f(j)^p b ^{jp}=\sum_{j=0,\dots ,7}f(j) b ^{jp}=$

$=\sum_{j=0,\dots ,7}f(jp^2) b ^{jp}=f(p)\sum_{j=0,\dots ,7}f(jp) b ^{jp}$
Il primo p è dispari, sicché b^p è un generatore di <b> ⇒ {b^jp | j=0,…,7}={b^j | j=0,…,7}.

Prime proprietà del simbolo di Legendre

Inoltre è facile verificare che ogni volta che b^j=b^j’, si ha anche f(j)=f(j’).

Da ciò segue che
$\sum_{j=0,\dots ,7}f(jp) b ^{jp}=\sum_{j=0,\dots ,7}f(j) b^j=G$ ,

e quindi G^p=f(p)G.

Conclusioni

Si è dunque provato che
$\left(\frac{2}{p}\right)G=f(p)G$
⇒ $\left(\frac{2}{p}\right)\equiv f(p) (mod \;p)$ , e quindi $\left(\frac{2}{p}\right)=f(p)=(-1)^{\frac{n^2-1}{8}}$

Legge di reciprocità quadratica

Lemma 12.8 (senza dimostrazione)
Siano p e q primi dispari distinti. Sia n un numero naturale positivo tale che pⁿ-1 sia un multiplo di q, e sia F un campo finito di ordine pⁿ. Sia b un elemento di F* di periodo q, e sia $G=\sum_{j=0, \dots , q-1}(\frac{j}{q})b ^j$ .
Allora $G^2=(-1)^{\frac{q-1}{2}}q$ .

Proposizione 12.9 (Legge di reciprocità quadratica)

Siano p e q primi dispari distinti. Allora $\left(\frac{p}{q}\right)=(-1)^{\frac{(p-1)(q-1)}{4}}\left(\frac{q}{p}\right)$ .
Dimostrazione Sia n un numero naturale positivo tale che pⁿ-1 sia un multiplo di q (ad esempio si può scegliere n=q-1), e sia F un campo finito di ordine pⁿ.
Sia b un elemento di F* di periodo q.
Si ponga ora

$G=\sum_{j=0, \dots , q-1}\left(\frac{j}{q}\right)b ^j$ ;

si calcolerà in due modi diversi G^p.

Legge di reciprocità quadratica

Primo Modo

$G^p=\left(G^2\right)^{\frac{p-1}{2}}G=\left(\left(-1\right)^{\frac{q-1}{2}}q\right)^{\frac{p-1}{2}}G=\left(-1\right)^{\frac{\left(q-1\right)\left(p-1\right)}{4}} q^{\frac{p-1}{2}} G=\left(-1\right)^{\frac{\left(q-1\right)\left(p-1\right)}{4}}\left\left(\frac{q}{p}\right)G$
Secondo Modo
$G^p=\left(\sum_{j=0,\dots ,7} \left(\frac{j}{q}\right) b ^j\right)^p=\sum_{j=0,\dots ,7}\left(\left(\frac{j}{q}\right) b ^j\right)^p=\sum_{j=0,\dots ,7}\left(\frac{j}{q}\right)^p b ^{jp}=$

$=\sum_{j=0,\dots ,7}\left(\frac{j}{q}\right) b ^{jp}=\sum_{j=0,\dots ,7}\left(\frac{jp^2}{q}\right) b ^{jp}=$

$=\left(\frac{p}{q}\right)\sum_{j=0,\dots ,7}\left(\frac{jp}{q}\right) b ^{jp}$

Legge di reciprocità quadratica

Il primo p è dispari, sicché b^p è un generatore di <b> ⇒ {b^jp | j=0,…,7}={b^j | j=0,…,7};
inoltre ogni volta che b^j=b^j’, si ha anche j≡j’ (mod 8) e quindi

$\left(\frac{j}{q}\right)=\left(\frac{j'}{q}\right)$ .

Da ciò segue che

$\sum_{j=0,\dots ,7}\left(\frac{jp}{q}\right) b ^{jp}=\sum_{j=0,\dots ,7}\left(\frac{j}{q}\right) b ^j=G$ ,

e quindi

$G^p=\left(\frac{p}{q}\right)G$ .

Legge di reciprocità quadratica

Conclusioni

Si è dunque provato che

$(-1)^{\frac{\left(q-1\right)\left(p-1\right)}{4}}\left(\frac{q}{p}\right)G=\left(\frac{p}{q}\right) G$
⇒ $\left(\frac{p}{q}\right)\equiv (-1)^{\frac{(p-1)(q-1)}{4}}\left(\frac{q}{p}\right) \; (mod \; p)$ ,