Matematica Discreta Lezione del giorno 16 dicembre 2011

(1)

Matematica Discreta

Lezione del giorno 16 dicembre 2011

Resta da risolvere il Problema 2 della precedente lezione:

dati i numeri naturali a, b, come calcolare gli interi relativi x,y tali che mcd(a,b)=ax+by ? Illustreremo un algoritmo (detto Algoritmo Euclideo esteso) per calcolare i coefficienti interi relativi x,y tali che mcd(a,b)=ax+by: tale algoritmo è basato sull’algoritmo Euclideo delle divisioni successive.

Se n è il numero delle divisioni successive effettuate nell’algoritmo Euclideo, lo schema di tali divisioni è il seguente:

divisione numero 1 a=bq

1

+r

1

con q

1

,r

1

interi 0, r

1

<b (se r

1

>0) divisione numero 2 b=r

1

q

2

+r

2

con q

2

,r

2

interi 0, r

2

<r

1

(se r

2

>0) divisione numero 3 r

1

=r

2

q

3

+r

3

con q

3

,r

3

interi 0, r

3

<r

2

(se r

3

>0) divisione numero 4 r

2

=r

3

q

4

+r

4

con q

4

,r

4

interi 0, r

4

<r

3

(se r

4

>0) divisione numero 5 r

3

=r

4

q

5

+r

5

con q

5

,r

5

interi 0, r

5

<r

4

. .

(se r

i-1

>0) divisione numero i r

i-2

=r

i-1

q

i

+r

i

con q

i

,r

i

interi 0, r

i

<r

i-1

. . .

(se r

n-2

>0) divisione numero (n-1) r

n-3

=r

n-2

q

n-1

+r

n-1

con q

n-1

,r

n-1

interi 0, r

n-1

<r

n-2

(se r

n-1

>0) divisione numero n r

n-2

=r

n-1

q

n

+r

n

con q

n

,r

n

interi 0, r

n

=0

Nell’ultima divisione numero n si è ottenuto resto r

n

=0 e si conclude che il penultimo resto r

n-1

è proprio il mcd(a,b).

Costruiamo i seguenti valori numerici: s

0

=1, t

0

=0, e notiamo che il resto

Osserviamo che: se il resto r

i-1

ed il resto r

i-2

si possono ciascuno esprimere come combinazione lineare di a,b a coefficienti interi relativi, allora anche il resto r

i

si può esprimere come combinazione lineare di a,b a coefficienti interi relativi. Per verificare tale affermazione basta supporre che r

i-1

si possa esprimere come combinazione lineare di a,b a coefficienti interi relativi che indicheremo con s

i

, t

i

:

r

i-1

= as

i

+ bt

i

e che r

i-2

si possa esprimere come combinazione lineare di a,b a coefficienti interi relativi che indicheremo con s

i-1

, t

i-1

:

r

i-2

= as

i-1

+ bt

i-1

e calcolare il valore del resto r

i

ricavandolo dalla divisione numero i:

r

i

=r

i-2

-r

i-1

q

i

=(as

i-1

+ bt

i-1

)-(as

i

+ bt

i

)q

i

=a(s

i-1

-s

i

q

i

)+b(t

i-1

-t

i

q

i

)

per concludere che in effetti il resto r

i

si può esprimere come combinazione lineare di a,b a coefficienti interi relativi s

i+1

=s

i-1

-s

i

q

i

, t

i+1

=t

i-1

-t

i

q

i

.

Ora i primi 2 resti r

1

, r

2

si possono esprimere certamente come combinazione lineare di a,b a coefficienti interi relativi perché dalla prima divisione si ricava:

r

1

=a-bq

1

(cioè r

1

si può esprimere come combinazione lineare di a,b a coefficienti interi relativi s

2

=1, t

2

= -q

1

) mentre dalla seconda divisione si ricava:

r

2

=b-r

1

q

2

=b-(a-bq

1

)q

2

=a(-q

2

)+b(1+q

1

q

2

)

(2)

(cioè r

2

si può esprimere come combinazione lineare di a,b a coefficienti interi relativi s

3

=-q

2

, t

3

= 1+q

1

q

2

). In questo modo, con il ragionamento precedente, si può allora esprimere il resto r

3

come combinazione lineare di a,b (perché r

1

,r

2

si possono esprimere in questo modo), poi il resto r

4

come combinazione lineare di a,b a coefficienti interi relativi (perché r

2

,r

3

si possono esprimere in questo modo) e così via fino ad esprimere alla fine il resto r

n-1

(che è il mcd(a,b)) come combinazione lineare di a,b a coefficienti interi relativi, e risolvere così il Problema 2.

Seguendo il ragionamento precedente si vede che è necessario costruire in forma ricorsiva 2 successioni di numeri interi relativi:

- la successione s

2

,s

3

,s

4

…….

- la successione t

2

,t

3

,t

4

,…….

che permettono di esprimere r

1

nella forma as

2

+bt

2,

di esprimere r

2

nella forma as

3

+bt

3

e così via , in generale esprimendo r

i

nella forma as

i+1

+bt

i+1

, e infine esprimendo r

n-1

=mcd(a,b) nella forma as

n

+bt

n

(quindi i coefficienti x,y cercati nel Problema 2 sono proprio x=s

n

, y=t

n

).

Nelle successioni così costruite vi sono regole ricorsive che legano ogni termine con i 2 termini che lo precedono, e che sono state trovate nel ragionamento precedente:

s

i+1

=s

i-1

-s

i

q

i

, t

i+1

=t

i-1

-t

i

q

i

(dove q

i

è il quoziente della divisione numero i).

Tali regole però non permetterebbero di calcolare i termini s

2

,s

3

(perché essi non hanno 2 termini che li precedono) né t

2

,t

3

(per lo stesso motivo).

A ciò si può ovviare definendo 2 termini “iniziali” per ognuna delle successioni, nel modo seguente:

s

0

=1, s

1

=0, t

0

=0, t

1

=1

Questo rende valida le regola ricorsive anche per i termini s

2

,s

3

e t

2

,t

3

. Infatti si ha : (dalla divisione numero 1) r

1

=a-bq

1

=as

2

+bt

2

dove s

2

=1, t

2

= -q

1

(vengono così rispettate le regole ricorsive s

2

=s

0

-s

1

q

1

, t

2

=t

0

-t

1

q

1

)

(dalla divisione numero 2) r

2

=b-r

1

q

2

=b-(a-bq

1

)q

2

=as

3

+bt

3

dove s

3

= -q

2

, t

3

= 1+q

1

q

2

(vengono rispettate di nuovo le regole ricorsive s

3

=s

1

-s

2

q

2

, t

3

=t

1

-t

2

q

2

)

Riassumendo: per calcolare i coefficienti interi relativi x,y che permettono di esprimere il mcd(a,b) nella forma ax+by (combinazione lineare di a,b) si devono eseguire le n divisioni dell’Algoritmo Euclideo (che servono per calcolare il mcd(a,b)) e costruire 2 le successioni:

s

0

,s

1

,s

2

,……. ; t

0

,t

1

,t

2,

…….

definite ricorsivamente dai valori iniziali s

0

=1, s

1

=0; t

0

=0, t

1

=1 e dalle regole ricorsive:

s

i+1

=s

i-1

-s

i

q

i

, t

i+1

=t

i-1

-t

i

q

i

(dove q

i

è il quoziente della divisione numero i).

Alla fine i coefficienti cercati sono proprio x=s

n

, y=t

n

.

Esempio: riprendiamo l’esempio della lezione precedente mcd(371,98)=7, in cui sono state effettuate n=5 divisioni successive:

371=983+77 q

1

=3, r

1

=77 98=771+21 q

2

=1, r

2

=21 77=213+14 q

3

=3, r

3

=14 21=141+7 q

4

=1, r

4

=7 14=72+0 q

5

=2, r

5

=0 ottenendo appunto 7=mcd(371,98).

La costruzione delle successioni s

i

e t

i

porta ai seguenti valori:

s

0

=1, s

1

=0, s

2

=s

0

-s

1

q

1

=1, s

3

=s

1

-s

2

q

2

= -1, s

4

=s

2

-s

3

q

3

= 4, s

5

=s

3

-s

4

q

4

= -5 t

0

=0, t

1

=1, t

2

= t

0

-t

1

q

1

= -3, t

3

= t

1

-t

2

q

2

=4, t

4

= t

2

-t

3

q

3

= -15, t

5

= t

3

-t

4

q

4

= 19

da cui si ricava x=s

5

=-5, y=t

5

=19 e infine 7= mcd(371,98)=371•(-5)+98•19 .

Un’applicazione di questi risultati si trova nella ricerca di soluzioni intere di una equazione di primo

grado in 2 incognite x,y della forma seguente:

(3)

ax + by = c dove a,b,c sono numeri naturali fissati.

Si dimostra il seguente risultato:

l’equazione ha soluzioni intere in x,y  mcd(a,b) è divisore di c.

Dimostriamo l’implicazione :

Se esistono due valori interi x=x

0

, y=y

0

che risolvono l’equazione, si ha ax

0

+ by

0

= c, e se d=mcd(a,b) essendo d divisore comune di a,b esistono numeri naturali s,t tali che ds=a, dt=b, da cui c=ax

0

+by

0

=dsx

0

+dty

0

=d(sx

0

+ty

0

) e si ha che d è divisore di c, cioè la tesi.

Dimostriamo l’implicazione :

Se d=mcd(a,b) è divisore di c, esiste un numero naturale t tale che dt=c; ma dai ragionamenti precedenti segue che è possibile esprimere d come combinazione lineare di a,b

d= ax’+by’ a coefficienti interi relativi x’,y’

da cui si ha:

c=dt=ax’t+by’t

dunque l’equazione ax + by = c ha soluzioni intere x=x’t, y=y’t , cioè la tesi.

Esempio: l’equazione 12x+8y=10 non ha soluzioni intere in x,y perché mcd(12,8)=4 non è divisore di 10. Invece l’equazione:

371x+98y=14

ha soluzioni intere in x,y perché (vedere esempio precedente) mcd(371,98)=7 è divisore di 14.

Per trovare le effettive soluzioni in x,y si può seguire il procedimento illustrato nella dimostrazione dell’implicazione  vista sopra: essendo 7=mcd(371,98) divisore di c=14, esiste un numero naturale t tale che 7t=14 (ed è t=2). Dagli esempi precedenti sappiamo che è possibile esprimere 7=mcd(371,98) come combinazione lineare della forma 371x’+98y’ dove x’= -5, y’=19.

Soluzioni intere dell’equazione 371x+98y=14 sono allora x=x’t= -10, y=y’t=38.

Numeri primi

Sia a un qualunque numero naturale. Dall’eguaglianza a=a•1 segue che a,1 sono in ogni caso divisori di a (detti divisori banali di a).

Definiamo numero primo un numero naturale a>1 i cui unici divisori sono i divisori banali 1,a . Nota: osserviamo che, nella definizione di numero primo, il numero naturale 1 non è considerato primo. Il motivo di questa esclusione del numero 1 dai numeri primi sarà chiarito nella dimostrazione del “Teorema di fattorizzazione unica”.

Nota: nell’agosto del 2008 è stato trovato il più grande numero primo attualmente conosciuto (esso ha quasi 13.000.000 cifre in base 10).

Utili notizie possono essere trovate sul sito www.mersenne.org Fattorizzazione in primi

Dimostreremo che i numeri primi sono come i “mattoni” elementari con cui si possono “costruire “ tutti i numeri naturali >1, nel senso che ogni numero naturale >1 è prodotto di numeri primi e tale rappresentazione è sotto certi aspetti “unica”. Ricordiamo che per convenzione il termine

“prodotto” si intende al limite anche con 1 solo fattore (nel quale caso il risultato del prodotto è l’unico fattore coinvolto).

Premettiamo un risultato preliminare sui numeri primi:

(4)

Teorema.

Se a è un numero primo e se a é divisore del prodotto di 2 numeri naturali b,c allora a è divisore di almeno uno dei fattori b,c.

Dimostrazione:

Per assurdo supponiamo che a non sia divisore né di b né di c.

Essendo per ipotesi a(bc) esiste un numero naturale t tale che at=bc.

Poniamo d=mcd(a,b). Essendo da, db ed essendo a numero primo, si ha d=1 oppure d=a. Ma non può essere d=a (perché d è divisore di b mentre a non lo è) dunque è d=1. Per una proprietà del mcd(a,b), esistono 2 interi relativi x, y tali che d=1=ax+by. Moltiplicando ambo i membri per c e tenendo conto che at=bc si ha:

c=acx+bcy=acx+aty=a(cx+ty) e si ottiene ac (contraddizione).

Osservazione. Il risultato ora dimostrato si può estendere facilmente al caso del prodotto di 3 o più fattori.

Per esempio se il numero primo a è divisore di un prodotto bcd di 3 numeri naturali b,c,d allora, utilizzando la proprietà associativa del prodotto, si può osservare che a sarà divisore del prodotto (bc)d di 2 fattori bc,d dunque (utilizzando la proprietà precedente valida per 2 fattori) si otterrà a(bc) oppure ad, e di nuovo applicando la proprietà precedente sarà ab oppure ac oppure ad, quindi a sarà divisore di almeno uno dei 3 fattori b,c,d.