Vai alla Home Page About me Courseware Federica Living Library Federica Federica Podstudio Virtual Campus 3D Le Miniguide all'orientamento Gli eBook di Federica La Corte in Rete
 
 
Il Corso Le lezioni del Corso La Cattedra
 
Materiali di approfondimento Risorse Web Il Podcast di questa lezione

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 Zp*.
Si dice che a è un resto quadratico modulo p se [a]p è un quadrato in Zp*.
Si dice che a è un non-resto quadratico modulo p se [a]p non è un quadrato in Zp*.

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 Zp* ⇒  \left([a]_p^{\frac{p-1}{2}}\right)^2=[a]pp-1=[1]p .
D’altra parte Zp* è ciclico ⇒  [-1]p è l’unico elemento di periodo 2 di Zp* ⇒  [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 Zp* , e sia n un numero intero tale che [a]p=[g]pn .
D’altra parte
\left(\frac{a}{p}\right)=1 ⇒ [a]p è un  quadrato  in Zp*⇔ 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 n2-1 è un multiplo di 8.

Dimostrazione 

Esiste un numero k appartenente a N0 tale che n=2k+1  ⇒  n2-1=(2k+1)2-1=4k2+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 N0 ,
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 N0 ,si ha f(mn)=f(m)f(n).

Prime proprietà del simbolo di Legendre

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

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

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é bp è un generatore di <b>  ⇒  {bjp | j=0,…,7}={bj | j=0,…,7}.

Prime proprietà del simbolo di Legendre

Inoltre è facile verificare che ogni volta che bj=bj’ , 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 Gp=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 pn-1 sia un multiplo di q, e sia F un campo finito di ordine pn. 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 pn-1 sia un multiplo di q (ad esempio si può scegliere n=q-1), e sia F un campo finito di ordine pn.
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 Gp.

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é bp è un generatore di <b>  ⇒  {bjp | j=0,…,7}={bj | j=0,…,7};
inoltre ogni volta che bj=bj’ , 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),

e quindi

\left(\frac{p}{q}\right) = (-1)^{\frac{(p-1)(q-1)}{4}}\left(\frac{q}{p}\right).

  • Contenuti protetti da Creative Commons
  • Feed RSS
  • Condividi su FriendFeed
  • Condividi su Facebook
  • Segnala su Twitter
  • Condividi su LinkedIn
Progetto "Campus Virtuale" dell'Università degli Studi di Napoli Federico II, realizzato con il cofinanziamento dell'Unione europea. Asse V - Società dell'informazione - Obiettivo Operativo 5.1 e-Government ed e-Inclusion