note di matematica discreta - Aracne editrice · Nuove tecniche algebriche e nuovi metodi di...

note di matematica discreta

parte seconda (capitoli 6–10)

Maria Welleda BaldoniCiro Ciliberto

Giulia Maria Piacentini Cattaneo con la collaborazione di A. Calabri

Copyright © MMIII ARACNE EDITRICE S.r.l.

00173 Roma, via R. Garofalo, 133 a/b

tel. 06 93781065 – fax 06 72678427

www.aracneeditrice.it

[email protected]

ISBN 88-7999-457-3

I diritti di traduzione, di memorizzazione elettronica,di riproduzione e di adattamento anche parziale,

con qualsiasi mezzo, sono riservati per tutti i Paesi.

Non sono assolutamente consentite le fotocopiesenza il permesso scritto dell’Editore.

I edizione: febbraio 2003

SONO CONTRAFFATTE LE COPIE SPROVVISTE DEL CONTRASSEGNO SIAE

Capitolo 6

Nuove tecniche algebriche e

nuovi metodi di fattorizzazione

Le nozioni che introdurremo in questo capitolo, ossia i campi finiti,

la legge di reciprocita quadratica, le frazioni continue, sono uno svilup-

po naturale di concetti presentati nella prima parte del corso, e sono

importanti in se. Tuttavia la scelta di tali argomenti e stata fatta so-

prattutto in vista di alcune applicazioni. Ad esempio alla crittografia e

ai codici, come vedremo nei prossimi capitoli, o alla fattorizzazione di

interi e a test di primalita, questioni sulle quali torneremo piu avanti

in questo stesso capitolo e nei prossimi.

6.1. Campi finiti

In questo paragrafo introdurremo brevemente i campi finiti, cioe i

campi con un numero finito di elementi. Abbiamo gia visto che ogni

anello Zp, con p primo, e un campo finito, dato che ogni suo elemento

non nullo e invertibile.

E importante osservare che c’e una proprieta che distingue i campi

Zp dai sottocampi dei numeri complessi. Nel caso dei campi Zp accade

che sommando l’unita del campo con se stessa un opportuno numero di

volte si ottiene lo zero, mentre nel caso dei sottocampi di C questo non

avviene mai. Ad esempio, se consideriamo il campo Z5, se sommiamo

5 volte la classe unita 1 otteniamo la classe 0 cioe

1 + 1 + 1 + 1 + 1 = 0.

La stessa cosa accade se sommiamo 10, o 15, o 20 volte 1: otteniamo

sempre la classe 0, mentre comunque sommiamo l’unita 1 in Q otte-

niamo sempre qualcosa che e diverso da zero. Formalizziamo questa

proprieta nella seguente definizione.

270 6. NUOVE TECNICHE ALGEBRICHE

Definizione 6.1.1. Un campo K si dice di caratteristica finita o po-

sitiva se esiste un intero positivo m tale che

m1 = 1 + 1 + · · ·+ 1︸︷︷︸m addendi

= 0,

dove 1 e l’elemento unita di K, mentre si dice di caratteristica zero se

un tale m non esiste. Indicato con p il piu piccolo intero positivo tale

che p1 = 0, chiameremo p la caratteristica del campo K.

Dunque C, R, Q hanno tutti caratteristica zero, mentre Z5 ha ca-

ratteristica 5, Z13 ha caratteristica 13, in generale Zp ha caratteristica

p (cfr. esercizio A6.2.4). Se ricordiamo (cfr. pag. 108) la nozione di

periodo o ordine di un elemento di un gruppo, la caratteristica di un

campo altro non e che il periodo additivo dell’unita del campo.

Si puo dimostrare che se un campo ha caratteristica positiva, questa

e sempre un numero primo (cfr. esercizio A6.2.5).

Se un campo e finito, la sua caratteristica e positiva (cfr. esercizio

A6.2.6), ma non e vero il viceversa, cioe non e detto che, se la caratte-

ristica di un campo e positiva, allora il campo e finito. Basti pensare

al seguente esempio: sia Zp[x] l’anello dei polinomi a coefficienti nel

campo Zp e sia

Zp(x)def=

{f(x)

g(x)

∣∣∣∣ f(x), g(x) ∈ Zp[x], g(x) �= 0}

l’insieme di tutte le funzioni razionali a coefficienti in Zp nell’indeter-

minata x. E facile verificare che si tratta di un campo che contiene

Zp ed e di caratteristica positiva (precisamente di caratteristica p) ed

e infinito.

Dato un qualunque campo K si chiama sottocampo primo o fonda-

mentale di K l’intersezione di tutti i sottocampi di K. In sostanza il

sottocampo fondamentale di K e il piu piccolo sottocampo di K. Poiche

ogni sottocampo di K contiene 0 e 1, il sottocampo fondamentale e al-

tresı il piu piccolo sottocampo di K contenente 0 e 1. Tenendo conto di

cio il Lettore verifichera agevolmente che il sottocampo fondamentale

di C, R, e Q e il campo Q dei razionali mentre il sottocampo fonda-

mentale di un qualunque campo di caratteristica p e il campo Zp (cfr.

esercizi A6.2.7 e A6.2.8).

6.1. CAMPI FINITI 271

Una estensione (o ampliamento) di un campo F e un campo K che

contiene F. Ad esempio, R e un’estensione di Q, C e un’estensione di

Q e di R, Zp(x) e una estensione di Zp.

Ogni campo e estensione del suo sottocampo fondamentale. Se in

particolare siamo interessati a studiare i campi finiti, questi avranno,

come si e visto, caratteristica positiva p e pertanto saranno estensione

del loro sottocampo fondamentale Zp. Dato che ogni campo K esten-

sione di un campo F si puo pensare come spazio vettoriale su F, ogni

campo finito deve avere pn elementi, essendo p un numero primo e n la

dimensione dello spazio vettoriale K su Zp: infatti i suoi elementi sono

tutte le combinazioni lineari a coefficienti in Zp degli n elementi di una

base, e dunque sono esattamente pn. Questo ci dice intanto che non

esistono campi finiti con 20 o con 24 elementi, perche ne 20 ne 24 sono

potenze di primi.

Se K e un’estensione di un sottocampo F, la dimensione di K come

spazio vettoriale su F si dice grado dell’estensione e si indica col simbolo

[K : F]. Il grado [K : F] puo essere anche infinito. D’ora in poi noi

saremo sempre in situazioni in cui invece [K : F] e finito, poiche avremo

a che fare con campi finiti. E importante osservare allora che, se K e

estensione di F che a sua volta e estensione di H, allora ovviamente K

e pure estensione di H e si ha il cosidetto teorema di moltiplicazione

dei gradi

[K : H] = [K : F] · [F : H] (6.1.1)

di cui lasciamo la dimostrazione al Lettore (cfr. esercizio A6.2.9).

Valgono le seguenti due proprieta:

• dati comunque un numero primo p e un intero positivo n esiste un

campo con pn elementi;

• due campi con pn elementi sono isomorfi.

Accenniamo brevemente a come si fa a costruire un campo con pn

elementi a partire da un qualunque primo p e un qualunque intero

positivo n. Innanzitutto si osserva che in un campo di caratteristica p

vale l’identita fondamentale, detta, per motivi che non sfuggiranno al

Lettore, sogno della matricola:

(a+ b)p = ap + bp (6.1.2)


valida per ogni coppia di elementi a e b del campo (cfr. eserc. A6.2.10).

Si considera poi il polinomio a coefficienti in Zp

f(x) = xpn − x. (6.1.3)

Tenendo presente il sogno della matricola, si dimostra che l’insieme

delle radici di questo polinomio costituisce un campo (cfr. esercizio

A6.2.11), che e il cosiddetto campo di spezzamento di f(x), ossia un

campo K ⊇ F nel quale f si spezza in fattori lineari e che e il piu

piccolo campo che gode di questa proprieta, nel senso che il polinomio

f(x) non si spezza in fattori lineari in nessun altro campo K′ ⊂ K.

Poiche p = 0 in un campo di caratteristica p, si ha che la derivata di

f(x) e −1, e quindi f(x) e la sua derivata non hanno radici comuni. Nesegue che le radici di f(x) sono tutte distinte e quindi sono in numero

di pn. Questo completa la dimostrazione dell’esistenza di un campo

con pn elementi.

Notiamo ancora che ogni campo K con pn elementi e un campo di

spezzamento del polinomio xpn − x su Zp. Ossia i suoi elementi sono

tutte e sole le radici del polinomio xpn − x. Questo e ovviamente vero

per 0. Inoltre se x ∈ K e diverso da zero, si ha xpn−1 = 1 e quindi

xpn −x = 0. Infatti se x1, . . . , xh, con h = pn −1, sono gli elementi nonnulli di K, si ha

xh(x1 · · · xh) = (xx1) · · · (xxh)

Ma xx1, . . . , xxh coincidono, a meno dell’ordine, con x1, . . . , xh e quindi

xh(x1 · · · xh) = x1 · · · xh

da cui segue xh = 1.

Un teorema fondamentale della teoria dei campi afferma che il cam-

po di spezzamento di un polinomio e unico a meno di isomorfismi. Ne

segue che due campi finiti con pn elementi sono tra di loro isomorfi.

A parte l’aspetto teorico, le considerazioni appena fatte ci permet-

tono, da un punto di vista operativo, di costruire ogni campo finito di

ordine pn per ogni primo p e ogni intero positivo n: esso e semplice-

mente l’insieme di tutte le radici del polinomio xpn − x. Tale campo

finito, unico a meno di isomorfismi, si indica col simbolo Fpn .

Vediamo ora qualche esempio.


• Campo F4 di ordine quattro

Si tratta di un’estensione di grado due di Z2. I suoi elementi sono

le radici del polinomio

x4 − x.

Notiamo che

x4 − x = x(x − 1)(x2 + x+ 1)

Le radici sono quindi 0, 1, e le due radici del polinomio x2 + x + 1.

Indicata con α una radice di x2+x+1, risulta α2 = α+1 in quanto in

un campo di caratteristica 2 si ha 1 = −1. L’altra radice di x2 + x+ 1

e allora α+ 1. Infatti (α + 1)2 + (α+ 1) + 1 = α2 + 1+ α+ 1+ 1 = 0.

Quindi:

F4 = {0, 1, α, β}dove β = α + 1 = α2. Le tavole di addizione e moltiplicazione del

campo sono le seguenti:

+ 0 1 α β

0 0 1 α β

1 1 0 β α

α α β 0 1

β β α 1 0

· 0 1 α β

0 0 0 0 0

1 0 1 α β

α 0 α β 1

β 0 β 1 α

Possiamo anche trovare il campo di ordine 4 in altro modo, che non

comporta la ricerca delle radici del polinomio x4 − x. A tale scopo si

usano concetti introdotti nell’appendice a questo capitolo. Basta cioe

trovare un polinomio irriducibile f(x) di grado 2 su Z2 e considerare

l’anello dei polinomi a coefficienti in Z2 modulo f(x) (cfr. pag. 322).

Ora, c’e un unico polinomio irriducibile di grado 2 su Z2, precisamente

x2 + x + 1 (cfr. esercizio A6.2.12). Consideriamo quindi i polinomi di

Z2[x] con la condizione che x2 + x + 1 = 0, ossia x2 = x + 1. Stiamo

dunque identificando due polinomi f(x) e g(x) quando la loro differenza

e un multiplo di x2 + x+ 1:

f(x) ≡ g(x) (mod x2 + x+ 1) (6.1.4)

Come gia osservato per x = α, si ha:

x2 ≡ x+ 1 (mod x2 + x+ 1) (6.1.5)


Inoltre:

x3 ≡ 1 (mod x2 + x+ 1)

perche x3 − 1 = (x − 1)(x2 + x+ 1). E ancora

x5 + x4 + 1 ≡ 0 (mod x2 + x+ 1)

perche x5 + x4 + 1 = (x3 + x+ 1)(x2 + x+ 1).

Dunque, ogni volta che troviamo x2 in un polinomio, possiamo sem-

plicemente sostituirlo con x + 1, quando troviamo x3 possiamo sosti-

tuirlo con 1, quando troviamo x4 possiamo sostituirlo con x e cosı via.

Ad esempio il polinomio

x4 + x+ 1

viene identificato con il polinomio 1. Analoghe considerazioni si appli-

cano quando si lavora modulo un qualunque altro polinomio.

Ad ogni modo, la (6.1.4) e una relazione di equivalenza (cfr. eser-

cizio A6.2.1) e, tenendo presente la formula (6.1.5), si vede che in ogni

classe di equivalenza esiste un polinomio lineare (cfr. esercizio A6.2.3).

L’insieme quoziente si indica con

Z2[x]/(x2 + x+ 1)

ed e un campo i cui elementi sono le quattro classi

0, 1, x, 1 + x.

• Campo F8 di ordine otto

Si tratta di una estensione di Z2 di grado 3. I suoi elementi sono

tutte e sole le radici del polinomio

x8 − x.

La fattorizzazione di x8 − x in fattori irriducibili su Z e

x8 − x = x(x − 1)(x6 + x5 + x4 + x3 + x2 + x+ 1) (6.1.6)

(cfr. esercizio A6.2.13). Ma l’ultimo fattore si spezza in due fattori

irriducibili su Z2, cioe la fattorizzazione di x8 − x su Z2 e la seguente

(cfr. esercizio A6.2.14):

x8 − x = x(x − 1)(x3 + x+ 1)(x3 + x2 + 1). (6.1.7)


Anziche trovare tutte le radici di questo polinomio, conviene scegliere

uno dei due polinomi irriducibili di terzo grado su Z2 della fattorizza-

zione di x8 − x, ad esempio x3 + x + 1, e osservare che F8 e isomorfo

a Z2[x]/(x3 + x + 1). Infatti questo quoziente e un campo con esatta-

mente 8 elementi, e quindi non puo essere che F8. Analogamente al

caso precedente, ogni classe modulo x3 + x + 1 e individuata da un

polinomio di grado al piu due, in quanto possiamo identificare x3 con

x+ 1, x4 con x2 + x, x5 con x2 + x+ 1, x6 con x2 + 1, x7 con 1 e cosı

via. Indicata dunque con α una radice di x3 + x+ 1, o tale che

α3 = α + 1,

il campo F8 sara costituito dai seguenti elementi:

F8 = {a0 + a1α+ a2α2 | ai ∈ Z2} =

= {0, 1, β, β2, 1 + β, 1 + β2, β + β2, 1 + β + β2}.Lasciamo al Lettore il compito di scrivere le tabelle di addizione e

di moltiplicazione di questi elementi (cfr. esercizio A6.2.15). Notiamo

altresı che F4 non e un sottocampo di F8 perche questo sarebbe in

contraddizione col teorema di moltiplicazione dei gradi, in quanto [F8 :

F2] = 3 e [F4 : F2] = 2, e 2 non divide 3. Il Lettore potra verificare

direttamente dalle tabelle di addizione e moltiplicazione scritte dianzi

che l’unico sottocampo di F8 e F2 e che la stessa proprieta vale per F4.

• Campo F16 di ordine sedici

E un’estensione di grado 4 di Z2. I suoi elementi sono le radici del

polinomio

x16 − x.

La fattorizzazione di x16 − x in fattori irriducibili in Z[x] e la seguente

(cfr. esercizio A6.2.16):

x16 − x = x(x − 1)(x2 + x+ 1)(x4 + x3 + x2 + x+ 1) ·· (x8 − x7 + x5 − x4 + x3 − x+ 1)

(6.1.8)


ma su Z2 si ha la seguente fattorizzazione in polinomi irriducibili (cfr.

esercizio A6.2.17):

x16 − x = x(x − 1)(x2 + x+ 1)(x4 + x+ 1) ·· (x4 + x3 + 1)(x4 + x3 + x2 + x+ 1)

(6.1.9)

Il Lettore verifichera facilmente che F8 non e un sottocampo di F16,

mentre F4 lo e (cfr. esercizio A6.2.18).

• Campo F9 di ordine nove

Si parte da Z3 e si considera il polinomio

x9 − x = x(x4 − 1)(x4 + 1) =

= x(x − 1)(x+ 1)(x2 + 1)(x4 + 1) =

= x(x − 1)(x+ 1)(x2 + 1)(x2 + x − 1)(x2 − x − 1)(6.1.10)

(cfr. esercizio A6.2.19). Per ottenere F9 basta considerare, analoga-

mente a quanto fatto dianzi, Z3[x]/(x2 + 1). Ancora una volta ogni

classe di equivalenza modulo x2 + 1 contiene un polinomio di grado al

piu 1. Se indichiamo con i, come si fa in C, una radice di x2 + 1, si ha

F9 = {a0 + a1i| ai ∈ Z3} == {0, 1, i,−1,−i, 1 + i, 1− i,−1 + i,−1− i}.

Il Lettore non avra difficolta a scrivere le tabelle di addizione e mol-

tiplicazione degli elementi di F9 scritti in questo modo (cfr. esercizio

A6.2.20). Invece di procedere cosı, possiamo anche riguardare F9 come

Z3[x]/(x2 − x − 1). Anche in questo caso ogni classe di equivalenza in

Z3[x]/(x2 − x − 1) contiene un polinomio di grado al piu 1. Quindi,

se indichiamo con α una radice del polinomio x2 − x − 1 irriducibilesu Z3, ovvero un elemento tale che α2 = α + 1, si vede che F9 risulta

costituito dai seguenti 9 elementi:

0, 1, 2, α, 2α, 1 + α, 1 + 2α, 2 + α, 2 + 2α.

Si ha allora α = −1 ± i. E interessante notare che gli elementi non

nulli di F9 risultano tutti potenze di α (cfr. esercizio A6.2.21), mentre

ovviamente non e vera la stessa cosa in relazione ad i, in quanto le

potenze distinte di i sono solo 4 e cioe i0 = 1, i1 = i, i2 = −1, i3 = −i,

6.2. CONGRUENZE POLINOMIALI NON LINEARI 277

mentre i4 = 1. Si dice allora che il gruppo moltiplicativo F∗9 = F9 \ {0}

di F9 e un gruppo ciclico generato da α.

Ricordiamo che un gruppo G, munito dell’operazione ·, si dice ci-clico se esiste un elemento x di G tale che ogni elemento di G si puo

scrivere come una potenza xn di x. In tal caso l’elemento x si dice un

generatore di G.

L’ultima proprieta messa in luce in relazione a F9 e un caso parti-

colare di un importante fatto generale, espresso dal seguente:

Teorema 6.1.2. Il gruppo moltiplicativo di ogni campo finito e ciclico.

A titolo di esempio il Lettore puo dimostrare l’enunciato di questo

teorema per i campi F4, F8 e F16 considerati dianzi (cfr. esercizi A6.2.22,

A6.2.23 e A6.2.24).

Disporre di un generatore del gruppo moltiplicativo di un campo

finito e assai utile, specialmente nelle applicazioni pratiche di tipo com-

putazionale, in quanto ogni elemento del campo si puo allora scrivere

in modo semplice come potenza del generatore in questione. Tuttavia,

le considerazioni fatte a proposito di F9 mostrano che le costruzioni

dei campi finiti che possono sembrare le piu ovvie non danno in modo

naturale un generatore del gruppo moltiplicativo del campo. In ge-

nerale determinare un tale generatore e un problema computazionale

alquanto delicato.

6.2. Congruenze polinomiali non lineari

Consideriamo una congruenza del tipo

f(x) ≡ 0 (mod m)

dove f(x) =∑n

i=0 aixi e un polinomio in x a coefficienti interi del quale

cerchiamo soluzioni modulo un intero positivo m arbitrario.

Una congruenza di questo tipo e ad esempio la seguente:

x2 + 2x − 3 ≡ 0 (mod 121). (6.2.1)

Per grado di una congruenza si intende l’esponente massimo di x il

cui coefficiente non e divisibile per m. Il grado (6.2.1) e 2.

Nel capitolo 2 abbiamo studiato le congruenze lineari. Quelle che

studieremo ora sono le congruenze polinomiali non lineari. La loro


soluzione e uno dei maggiori problemi in teoria dei numeri e presenta

ancora molti problemi irrisolti. Accenneremo ora a qualche risultato re-

lativo alle congruenze polinomiali non lineari, con particolare riguardo

a quelle di grado 2.

Partiamo dal caso in cui m sia un numero primo p. Osserviamo che

un polinomio a coefficienti in un campo non puo avere piu radici del

suo grado (cfr. esercizio A5.1.9). Allora la congruenza

f(x) ≡ 0 (mod p),

dove p e primo, non potra avere piu di n soluzioni, se n e il grado di

f(x), dato che i coefficienti si possono pensare appartenenti a Zp.

Cio non e vero rispetto ad un modulo non primo. Ad esempio la

congruenza

x2 − 1 ≡ 0 (mod 8)

ammette 4 soluzioni, cioe x = 1, 3, 5 e 7.

Facciamo alcuni esempi.

Esempio 6.2.1. Risolvere la congruenza x3 + 2x2 − 1 ≡ 0 (mod 5).Per trovare tutte le soluzioni basta sostituire in f(x) = x3+2x2−1

i valori x = 0, 1, 2, 3, 4 e vedere se l’intero che si ottiene e o no congruo

a 0 modulo 5. Si ha dunque:

x 0 1 2 3 4

f(x) −1 2 15 44 95

I valori di x che sono soluzione della f(x) ≡ 0 (mod 5) sono pertantox = 2 e x = 4. Si osservi che sarebbe stato piu semplice, dal punto di

vista computazionale, scegliere x = 1, 2,−1,−2, avendo cosıx 0 1 2 −2 −1

f(x) −1 2 15 −1 0

Otteniamo allora le soluzioni x = 2 e x = −1 ≡ 4 (mod 5).Esempio 6.2.2. Risolvere la congruenza x3 + 2x2 − 1 ≡ 0 (mod 7).


Calcoliamo f(x) = x3 + 2x2 − 1 in corrispondenza ai valori x =

0, 1, 2, 3, 4, 5, 6, ovvero x = 0, 1, 2, 3,−3,−2,−1, modulo 7:x 0 1 2 3 −3 −2 −1

f(x) −1 2 15 ≡ 1 44 ≡ 2 −10 ≡ 4 −1 0

La congruenza ammette la sola soluzione x = −1, cioe x = 6.

Esempio 6.2.3. Risolvere la congruenza x3 + 2x2 − 1 ≡ 0 (mod 10).Potremmo procedere come sopra, ossia valutando f(x) = x3+2x2−

1 per x = 0, 1, 2, . . . 9 modulo 10, e vedere per quali valori di x si ha

che f(x) e congruo a 0. Tuttavia conviene invece procedere al modo

seguente. Si ricordi che se m e n sono relativamente primi, allora a ≡ b

(mod mn) se e solo se a ≡ b (mod m) e a ≡ b (mod n). Questo

significa che la congruenza

x3 + 2x2 − 1 ≡ 0 (mod 10)

e equivalente al sistema di due congruenze⎧⎨⎩x3 + 2x2 − 1 ≡ 0 (mod 2),

x3 + 2x2 − 1 ≡ 0 (mod 5).

Ora, e facile vedere che la prima ammette come unica soluzione x = 1

(mod 2) mentre la seconda ammette, come si e visto nel primo esempio,

le soluzioni x = 2 (mod 5) e x = 4 (mod 5). Allora x e soluzione di

x3 + 2x2 − 1 ≡ 0 (mod 10) se e solo sex ≡ 1 (mod 2) e x ≡ 2 o 4 (mod 5).

A questo punto facciamo intervenire il teorema cinese dei resti 2.4.2 (cfr.

pag. 91). Sappiamo che ad ogni coppia di soluzioni modulo 2 e modulo

5 corrisponde una unica soluzione modulo 10, dato cheMCD(2, 5) = 1.

Si tratta allora di risolvere i due sistemi di congruenze lineari⎧⎨⎩x ≡ 1 (mod 2)

x ≡ 2 (mod 5)e

⎧⎨⎩x ≡ 1 (mod 2)

x ≡ 4 (mod 5)

Si ottengono cosı le due soluzioni x = 7 e x = 9 modulo 10. Il Lettore

potra ritrovare questo stesso risultato direttamente valutando f(x) per

x = 0, 1, 2, . . . 9 (cfr. esercizio A6.2.25).


Esempio 6.2.4. Risolvere la congruenza x3 + 6x2 + 1 ≡ 0 (mod 12).Si ha 12 = 3·4 eMCD(3, 4) = 1, quindi x e soluzione di x3+6x2+1

(mod 12) se e solo se⎧⎨⎩x3 + 6x2 + 1 ≡ 0 (mod 3)

x3 + 6x2 + 1 ≡ 0 (mod 4),

poi si procede come nell’esempio precedente (cfr. esercizio A6.2.26).

In questi esempi siamo riusciti a ridurre le congruenze di partenza

a congruenze modulo primi o potenze di numeri primi. Nel seguente

lemma proveremo che questo e vero sempre. Infatti proveremo che, in

generale, data una congruenza del tipo

f(x) ≡ 0 (mod m)

ci si puo ricondurre, per risolverla, alla risoluzione di congruenze poli-

nomiali della forma

f(x) ≡ 0 (mod pα), p primo, (6.2.2)

nonche, come negli esempi precedenti, ad un’applicazione del teorema

cinese dei resti.

Lemma 6.2.5. Sia m = pα11 pα2

2 · · · pαkk la fattorizzazione dell’intero po-

sitivo m in primi. Allora la congruenza polinomiale

f(x) ≡ 0 (mod m) (6.2.3)

e risolubile se e solo se e risolubile ciascuna delle congruenze f(x) ≡ 0(mod pαi

i ), per i = 1, 2, . . . , k.

Dimostrazione. Sia x0 soluzione della congruenza (6.2.3), cioe sia

f(x0) ≡ 0 (mod m). Dato che pαii |m per ogni i = 1, . . . , k, ne segue

che f(x0) ≡ 0 (mod pαii ) per ogni i = 1, . . . , k.

Viceversa, se esiste xi tale che f(xi) ≡ 0 (mod pαii ), per i = 1, . . . , k,

in virtu del Teorema cinese dei resti esiste x tale che x ≡ xi (mod pαii ),

per i = 1, . . . , k, e pertanto x e soluzione di (6.2.3). �


Osservazione 6.2.6. Applicando il precedente lemma e il teorema

cinese dei Resti, appare chiaro che se ogni congruenza

f(x) ≡ 0 (mod pαii )

ammette ti soluzioni, allora la congruenza (6.2.3) ha∏k

i=1 ti soluzioni.

Faremo ora vedere che, note le soluzioni della congruenza

f(x) ≡ 0 (mod p),

si possono trovare le soluzioni di f(x) ≡ 0 (mod pα), il che ci permette

di ridurre ogni congruenza polinomiale ad una congruenza modulo un

numero primo. Proveremo questo fatto mostrando che, per ogni intero

positivo α, le soluzioni di f(x) ≡ 0 (mod pα+1) sono ottenibili a partire

dalle soluzioni di f(x) ≡ 0 (mod pα).

Cominciamo discutendo un semplice esempio.

Esempio 6.2.7. Risolvere la congruenza

f(x) = x3 + 3x+ 2 ≡ 0 (mod 49). (6.2.4)

Possiamo evitare di calcolare f(x) per ogni x = 0, 1, . . ., 48,

notando che una soluzione di (6.2.4) e ovviamente anche soluzione di

f(x) = x3 + 3x+ 2 ≡ 0 (mod 7). (6.2.5)

Ma (6.2.5) e priva di soluzioni (cfr. esercizio A6.2.27), per cui anche

(6.2.4) non ha soluzioni.

Esempio 6.2.8. Risolvere la congruenza x4 + x+ 3 ≡ 0 (mod 25).La congruenza x4 + x + 3 ≡ 0 (mod 5) ha l’unica soluzione x =

1. Cio nonostante, la congruenza data non ha soluzioni, come si puo

verificare direttamente.

Si puo arrivare a questo risultato anche in altro modo, come conse-

guenza del seguente risultato:

Proposizione 6.2.9. Sia f(x) un polinomio a coefficienti interi, p un

primo e α un intero positivo. Se xα, con 0 ≤ xα < pα, e soluzione di:

f(x) ≡ 0 (mod pα) (6.2.6)


e t, con 0 ≤ t < p, e una soluzione di

f(xα)

pα+ tf ′(xα) ≡ 0 (mod p), (6.2.7)

allora xα+1 = xα + tpα e soluzione di:

f(x) ≡ 0 (mod pα+1). (6.2.8)

Viceversa, ogni soluzione xα+1, con 0 ≤ xα+1 < pα+1, della congruenza

(6.2.8) si ottiene nel modo suddetto.

Dimostrazione. Dimostriamo la prima parte della proposizione. Per

la formula di Taylor 5.5.6 possiamo scrivere:

f(xα+1) = f(xα + tpα) =

= f(xα) + tpαf ′(xα) +(tpα)2

2f (2)(xα) + · · ·+ (tp

α)n

n!f (n)(xα) ≡

≡ f(xα) + tpαf ′(xα) (mod pα+1)

in quanto pα+1 divide phα per ogni h ≥ 2. D’altra parte, la (6.2.7)

ci dice che f(xα)/pα + tf ′(xα) = Np, dove N e un intero. Quindi

f(xα) + tpαf ′(xα) = (Np)pα = Npα+1, da cui

f(xα+1) ≡ f(xα) + tpαf ′(xα) ≡ 0 (mod pα+1).

Viceversa, ogni soluzione della (6.2.8) e soluzione anche della (6.2.6).

Dunque se xα+1, con 0 ≤ xα+1 < pα+1, e tale che f(xα+1) ≡ 0

(mod pα+1), allora esiste un xα, con 0 ≤ xα < pα, tale che f(xα) ≡ 0(mod pα), con xα+1 ≡ xα (mod pα), ossia xα+1 = xα + tpα, con 0 ≤t < p. Usando di nuovo la formula di Taylor come sopra, si vede che

f(xα) + tpαf ′(xα) ≡ 0 (mod pα+1).

Poiche f(xα) ≡ 0 (mod pα), f(xα)pα e un intero N , ossia f(xα) = Npα,

da cui

f(xα)

pα+ tf ′(xα) = Npα + tpαf ′(xα) ≡ 0 (mod pα+1).

Dividendo per pα si ottiene N + tf ′(α) ≡ 0 (mod p). �

La precedente proposizione ci dice che se la congruenza di grado n

f(x) ≡ 0 (mod p) (6.2.9)

6.3. LA LEGGE DI RECIPROCITA QUADRATICA 283

ha ν (≤ n) soluzioni distinte modulo p, allora in generale la

f(x) ≡ 0 (mod pα)

ha anch’essa ν soluzioni distinte modulo pα. Ad esempio, se α = 2, per

ogni soluzione xα di (6.2.9), si ottiene un’unica soluzione di f(x) ≡ 0(mod p2), sempre che f ′(xα) non sia divisibile per p.

Esempio 6.2.10. Risolvere la congruenza x2 + 8 ≡ 0 (mod 121).Ci si riconduce a risolvere l’equazione

x2 + 8 ≡ 0 (mod 11)

cha ha le soluzioni x ≡ 5, 6 (mod 11). Queste conducono alla risolu-

zione delle seguenti congruenze lineari in t:

3− t ≡ 0 (mod 11), 4 + t ≡ 0 (mod 11),

che hanno soluzioni t ≡ 3 (mod 11) e t ≡ 7 (mod 11) rispettivamente.Corrispondentemente si trovano le soluzioni 5 + 3 · 11 = 38 (mod 121)e 7 + 6 · 11 = 73 modulo 121 della congruenza data.

6.3. La legge di reciprocita quadratica

Limitiamoci ora a congruenze polinomiali di secondo grado o, come

si dice, quadratiche ossia della forma

ax2 + bx+ c ≡ 0 (mod m).

In base ai risultati della sezione precedente possiamo supporre che il

modulo m sia un numero primo p. Anzi, dato che il caso p = 2 e

semplice, supporremo senz’altro che p sia un primo dispari. Sia data

pertanto la congruenza

ax2 + bx+ c ≡ 0 (mod p), p primo dispari, p� | a. (6.3.1)

Sia a′ ∈ Z tale che 2aa′ ≡ 1 (mod p): un tale a′ esiste sempreperche 2a �= 0 in Zp. Moltiplicando la (6.3.1) per 2a

′ si ottiene unacongruenza equivalente che e del tipo

x2 + 2b′x+ c′ ≡ 0 (mod p)


Essa si puo scrivere nella forma equivalente

(x+ b′)2 ≡ b′2 − c′ (mod p).

Ponendo y = x+ b′ e k = b′2 − c′, la (6.3.1) si riduce alla forma

y2 ≡ k (mod p). (6.3.2)

Per risolvere la (6.3.1) basta allora risolvere x+ b′ ≡ y (mod p) dove y

e soluzione della y2 ≡ k (mod p). Si noti che la congruenza x+ b′ ≡ y

(mod p) ammette sempre un’unica soluzione.

E stato Gauss il primo a notare che per risolvere congruenze qua-

dratiche e sufficiente risolvere congruenze del tipo particolare (6.3.2).

Esempio 6.3.1. Trovare le soluzioni della congruenza quadratica

2x2 + x+ 3 ≡ 0 (mod 5).

Utilizzando le stesse notazioni di sopra, determiniamo a′ ∈ Z tale

che 2 · 2a′ ≡ 1 (mod 5). Risulta a′ = −1. Moltiplicando la congruenzaper 2a′ = −2 si ottiene

x2 − 2x − 1 ≡ 0 (mod 5)

ossia

(x − 1)2 ≡ 2 (mod 5).

Posto y = x − 1, la congruenza da risolvere e pertanto lay2 ≡ 2 (mod 5).

Questa non ha soluzioni, e quindi neanche la congruenza originaria ha

soluzioni.

Esempio 6.3.2. Trovare le soluzioni della congruenza quadratica

3x2 + x+ 1 ≡ 0 (mod 5).

La congruenza e equivalente alla

(x+ 1)2 − 4 ≡ 0 (mod 5)

ossia a

y2 ≡ 4 (mod 5)

6.3. LA LEGGE DI RECIPROCITA QUADRATICA 285

che ammette due soluzioni y1 = 2 e y2 = 3. Quindi la congruenza

originaria 3x2 + x+ 1 ≡ 0 (mod 5) ha le due soluzioni x1 = y1 − 1 = 1e x2 = y2 − 1 = 2.Nei due esempi precedenti abbiamo trovato una congruenza del tipo

y2 ≡ k (mod p) che non ammette soluzioni, e una che ammette solu-

zioni. Vorremmo trovare dei criteri generali che permettano di decidere

quando una congruenza quadratica di tipo (6.3.2) ammette soluzioni e

quando non le ammette. E quanto ci accingiamo a fare.

Definizione 6.3.3. Sia p un primo dispari e a un intero tale che p� | a.Se la congruenza

x2 ≡ a (mod p)

e risolubile, allora a si dice residuo quadratico di p, altrimenti a si dice

non residuo quadratico di p.

In altri termini, un residuo quadratico di p e un elemento del gruppo

Z∗p = Zp \ {0} che e un quadrato. Parleremo quindi indifferentementedi residuo quadratico di p o di quadrato modulo p, ovvero di quadrato

in Z∗p. Guardando agli esempi precedenti, vediamo che 2 non e un

quadrato modulo 5, mentre 4 lo e.

In Z∗5 i quadrati sono:

1 = 12 = 42, 4 = 22 = 32.


1 = 12 = 62, 2 = 32 = 42, 4 = 22 = 52.


1 = 12 = 102, 3 = 52 = 62, 4 = 22 = 92,

5 = 42 = 72, 9 = 32 = 82.

Da questi esempi sembra di intuire che i quadrati sono esattamente

la meta degli elementi di Z∗p. Vale infatti la seguente proposizione:

Proposizione 6.3.4. Sia p un primo dispari. Allora i residui quadra-

tici di p sono esattamente in numero di (p − 1)/2 e sono i seguenti:

12, 22, . . . ,

(p − 32

)2

,

(p − 12

)2

.

note di matematica discreta - Aracne editrice · Nuove tecniche algebriche e nuovi metodi di...

Documents

Transcript of note di matematica discreta - Aracne editrice · Nuove tecniche algebriche e nuovi metodi di...