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
 
I corsi di Scienze Matematiche Fisiche e Naturali
 
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