MODULO PROF. VERARDI - unibo.itverardi/T d N Verardi, Introduzione.pdf · Riprenderemo questo...

Teoria dei numeri I 2013-14, modulo prof. Verardi – Introduzione

1

TEORIA DEI NUMERI I MODULO PROF. VERARDI

Prerequisit i obbligatori : insiemi, funzioni, relazioni d’equivalenza e d’ordine, operazioni e loro

proprietà; conoscenze di base dei numeri naturali ed interi; gruppi, anelli e campi; matrici e sistemi

lineari. Calcolo combinatorio.

INTRODUZIONE: alcuni argomenti che coinvolgono numeri interi:

A) Soluzioni intere.

B) Terne pitagoriche.

C) Numeri primi.

D) Tartaglia e Fibonacci.

Queste pagine anticipano alcuni argomenti, che a vario titolo entrano nella Teoria

dei Numeri, ed hanno lo scopo soprattutto di incuriosire e fornire lo spunto per

approfondimenti e ricerche personali.

Alcuni dei contenuti saranno svolti in seguito, in questo o nell’altro modulo, con

maggiore sviluppo ed anche con le doverose dimostrazioni. In particolare, il primo di essi,

sarà trattato più diffusamente nel capitolo su equazioni e sistemi lineari diofantei, ed

anticipa il problema di Frobenius sulle soluzioni intere non negative.

Il secondo, di cui si dà la formula finale con la dimostrazione di Klein, mostra un

esempio di equazione diofantea non lineare: a questo tipo di problemi sarà dedicato un

capitolo, sulle somme di quadrati e sulle forme quadratiche intere.

Di numeri primi si tratterà principalmente nell’altro modulo del corso: qui ci sono

alcune anticipazioni ed alcuni degli innumerevoli risultati legati a questi numeri.

Infine, l’ultima parte è dedicata ad un non così noto legame tra il triangolo di

Tartaglia ed i numeri di Fibonacci, e vuol essere anche un pretesto per ricordare

l’importanza di queste due nozioni.

NOTA. Per chi volesse ripassare gli argomenti di Algebra I sugli assiomi di Peano, la teoria della

divisibilità, i numeri primi ed il teorema di fattorizzazione, metto a disposizione in appendice il testo

delle lezioni di un modulo di Algebra I tenuto su questi argomenti nel 2012-13. Esso contiene per

completezza anche due costruzioni del campo razionale.


2

INTRODUZIONE

A) SOLUZIONI INTERE NON NEGATIVE. Sulla nota rivista “La Settimana

Enigmistica” sono presenti in ogni fascicolo numerosi giochi, che coinvolgono numeri

interi, generalmente numeri positivi.

In un numero recente, due personaggi, Gianni e Susy, sono in un negozio di dolciumi.

Gianni ha organizzato una festa, alla quale parteciperanno tra gli altri più di 40 signore. A

ciascuna egli vuole regalare un cioccolatino, come omaggio d’ingresso. La commessa del

negozio mostra solo confezioni di 7 e 9 cioccolatini ciascuna e Gianni osserva che non c’è

alcuna possibilità di acquistarle senza che avanzino cioccolatini. Invita perciò Susy a

indovinare quante saranno le signore presenti. Proviamoci noi.

Siano x ed y rispettivamente il numero di scatole da 7 e da 9 cioccolatini, ed n il numero

delle invitate. Sappiamo quindi che:

7x+9y ≥ n > 40.

x ≥ 0, y ≥ 0

Infine, n non è ottenibile nella forma 7x+9y.

Dalla domanda posta alla Susy, sembra di poter dedurre che la risposta sia unica, cioè che

esista un solo n > 40 che non è della forma 7x+9y, con x ed y non negativi. Senza questa

ultima limitazione, ogni numero intero è combinazione lineare di 7 e 9. Infatti, poiché

!

7 "4 + 9 " #3( ) = 1, allora per ogni n∈Z si ha

!

7 " 4n( ) + 9 " #3n( ) = n

Possiamo escludere tutti i multipli di 7 e di 9 maggiori di 40:

… 27, 28, 35, 36, 42, 45, 49, 54, 56, 63 ….

dato che è possibile acquistare zero scatole di uno dei due tipi.

Escludiamo ora i numeri > 40 che si ottengono sommando ad un multiplo di 9 un multiplo

di 7:

41 = 27+14, 43 = 36+7, 44 = 35+9, 46 = 28+18, 48 = 27+21,

50 = 36+14, 51 =42+9, …

È rimasto per ora il 47. Possiamo sottrarre via via 9, 18, 27, 36, 45 e scoprire che non

otteniamo mai un multiplo di 7, perciò 47 potrebbe essere il numero cercato. Se la

soluzione è unica, è certo n = 47.

Ma come fare a sapere che è l’unica?.


3

Fino a 63 = 9⋅7, si può procedere per tentativi, come fatto finora. Ma i numeri naturali sono

infiniti, quindi non si va molto avanti. Occorre un po’ di Algebra.

Abbiamo visto che in Z per ogni n intero si ha

!

7 " 4n( ) + 9 " #3n( ) = n .

Si ha anche

!

7 " 9t( ) + 9 " #7t( ) = 0 per ogni t intero. Allora si ha anche, sommando:

!

7 " 4n + 9t( ) + 9 " #3n #7t( ) = n

Ossia,

!

x = 4n + 9ty = "3n "7t

# $ %

. Per rendere y ≥ 0, occorre prendere t in modo che sia

!

t " # 3n7

. Affinché

sia x ≥ 0, occorre invece

!

t " # 4n9

. Quindi, in definitiva deve esistere un intero t tale che

!

"4n9

# t # " 3n7

. Si possono anche ridurre allo stesso denominatore le due frazioni:

!

"28n63

# t # " 27n63

. Allora è chiaro che se n = 63+h, con h positivo, allora

!

"27n63

" "28n63

#

$ % %

&

' ( ( =

n63

= 1+h63

> 1, quindi un intero t tra quelle due frazioni

!

"4n9

# t # " 3n7

esiste. Ne segue che per ogni n ≥ 63 una soluzione dell’equazione 7x+9y = n con x ed y non

negativi esiste.

Allora il solo numero maggiore di 40 che non si possa scrivere nella forma 7x+9y con x ed y

non negativi è 47, e questa è l’unica soluzione del problema posto da Gianni alla Susy.

Riprenderemo questo argomento, delle equazioni diofantee, in uno dei prossimi capitoli.

B) ANGOLI RETTI E TERNE PITAGORICHE. Un antichissimo problema, nato con

l’agricoltura e la conseguente costruzione delle prime città, riguarda la costruzione di

angoli retti.

La soluzione greca, basata sull’uso di riga e compasso, è ben nota: dapprima, tracciato con

la riga un segmento, col compasso si tracciano due circonferenze centrate negli estremi del

segmento e con raggio uguale al segmento stesso: congiungendo i due punti di intersezione

delle due circonferenze, si ottiene l’asse del segmento, perpendicolare al segmento nel suo

punto medio.

La perpendicolare da un punto ad una retta si ottiene sfruttando opportunamente questa

costruzione.


4

Per costruire la perpendicolare da un punto

esterno C ad una retta si traccia una

circonferenza secante, poi si trovano le due

intersezioni D, E: l’asse di DE passa per C e

CFD è retto. Se il punto G è sulla retta, una

circonferenza di centro G taglia la retta in due

punti H, I il cui asse passa per G ed è

perpendicolare alla retta.

Ma i popoli più antichi facevano davvero così, in particolare sul terreno o sulle pareti di

edifici? Certamente no.

In qualche modo avevano scoperto che

se un triangolo ha i lati di 3, 4, 5 unità

(di misura), allora l’angolo opposto al

lato maggiore è retto. Si tratta di un

caso particolare del Teorema di

Pitagora.

Basta fare 13 nodi equidistanti in una corda ed unire il primo col tredicesimo, (e così

restano 12) poi tendere la corda in modo da formare un triangolo nei cui lati ci sia il

numero giusto di spazi fra i nodi, 3, 4 e 5. Automaticamente l’angolo opposto al 5 è retto, a

meno di errori di realizzazione pratica.


5

Ciò pone un quesito: esistono altre terne di numeri interi positivi x, y, z che danno

luogo ad un triangolo rettangolo? Ciò avviene, per il teorema di Pitagora, se e solo se

!

x2 + y2 = z2.

Ovviamente, anche 6, 8 10 soddisfano questa condizione, e così 3k, 4k, 5k per ogni

!

k " 1. Interessano solo le terne primitive, ossia senza fattori comuni.

Tra queste terne si trova anche 5, 12, 13, ma ce ne sono altre? Ce ne saranno infinite?.

Intanto, sicuramente x ed y non hanno un fattore primo comune, altrimenti ce l’ha

anche z e la terna non è primitiva (e ciò vale anche per le altre coppie (x, z) ed (y,z). Ossia,

!

MCD x, y,z( ) = MCD x, y( ) = MCD x,z( ) = MCD y,z( ). In particolare, x ed y non sono entrambi pari. Potranno essere entrambi dispari? Un

numero dispari ha la forma 2k+1; allora

!

x2 + y2 = 4 k2 + k + h2 + h"

# $

%

& ' + 2 non può essere un

quadrato, perché è pari ma non è multiplo di 4. Allora uno è pari e l’altro è dispari. Quindi,

anche z è dispari.

Cerchiamo ora le terne primitive: le aveva già trovate Euclide, ma noi seguiremo un’idea del

matematico tedesco Felix Klein. Per questo però consideriamo anche le soluzioni negative,

quindi lavoriamo in Z anziché in N, cercando comunque le terne con z ≠ 0, poiché se z = 0

anche x = y = 0.

Inseriamo il problema nel piano cartesiano, dopo

aver diviso tutto per z, che non è nullo, ottenendo

il cerchio goniometrico

!

X2 + Y2 = 1. Sia

!

A = 0,"1( ) un punto della circonferenza. Le rette passanti per

A e diverse dall’asse Y hanno equazione

!

Y = mX "1.

Cerchiamo l’ulteriore punto

!

P = X, Y( ) di

intersezione con la circonferenza.

In particolare, cerchiamo le soluzioni razionali, ossia i punti P a coordinate razionali, che ci

daranno tutte e sole le terne pitagoriche. Se il punto P ha coordinate razionali X, Y, allora

anche il coefficiente angolare m è un numero razionale: basta ricordare che dalla formula

della retta per i due punti A e P si ricava

!

m =Y +1

X.


6

Risolviamo il sistema:

!

Y = mX "1X2 + Y2 = 1

#

X =2m

m2 +1

Y =m2 "1

m2 +1

$

%

& &

'

& &

$

%

& &

'

& &

. Si ricava quindi che, viceversa, se m è

razionale anche P ha le coordinate razionali. Poiché le sue coordinate sono quozienti

X = x/z, Y = y/z di interi, devono essere numeri razionali, quindi deve essere m = a/b, con a,

b interi coprimi (e b non nullo).

Allora, sostituendo, si ottiene:

!

X =2ab

a2 + b2

Y =a2 " b2

a2 + b2

#

$

% %

&

% %

'

x =2ab

a2 + b2(z

y =a2 " b2

a2 + b2(z

#

$

% %

&

% %

. Allora poniamo

!

z = a2 + b2 e

quindi avremo

!

x = 2ab, y = a2 " b2, z = a2 + b2.

Adesso è facile verificare che questa terna soddisfa la condizione

!

x2 + y2 = z2.

La verifica anche se a = 0 oppure se b = 0, o se x ed y sono interi negativi.

Ma avremo trovato terne primitive? Le avremo trovate tutte?

Sicuramente mancano quelle con z < 0, ma non è un grosso guaio: basta prendere

!

z = t " a2 + b2#

$ %

&

' ( , t = ±1, visto che al quadrato il segno poi diventa irrilevante. Allora

sicuramente le abbiamo trovate tutte, dato che da una terna primitiva troviamo il punto P e

la retta AP, che interseca la circonferenza nel punto razionale P e quindi con m razionale.

Piuttosto, come già osservato, se due dei tre numeri hanno un MCD = d ≠ 1, allora anche

ogni coppia (x, y), (x, z), (y, z) e la terna (x, y, z) hanno lo stesso MCD = d. Allora, se si vuole

che la terna sia primitiva, si dovrà prendere

!

z =t " a2 + b2#

$ %

&

' (

d, t = ±1.

In tal modo, si ottengono tutte le terne x, y, z primitive, al variare di a, b, con i loro segni.

Per semplicità, dato anche il problema iniziale, fissiamo z > 0, quindi prendiamo

!

t = 1. Ora

vediamo quanto può valere d. Ricordiamo che a e b sono coprimi, perché m = a/b era

ridotta ai minimi termini, quindi lo sono anche i loro quadrati.

Se d = 1, avremo

!

x = 2ab, y = a2 " b2, z = a2 + b2.

Se d > 1, esistono due interi u, v coprimi e tali che

!

a2 + b2 = d "u ,

!

a2 " b2 = d # v . Se ne

ricava:

!

2a2 = d " u + v( ) ,

!

2b2 = d " u # v( ) . Per quanto detto su

!

a2 e

!

b2, d non può dividere

entrambi, quindi deve dividere 2, ed allora d = 1 oppure d = 2.


7

Abbiamo finito? Ancora no: in realtà, il caso d = 2 si riconduce al caso d = 1. Basta un

piccolo artificio: in questo caso a e b devono essere dispari(*), ossia a = 2h+1, b = 2k+1.

Allora poniamo

!

p = h " k ,

!

q = h + k +1, e, dopo alcuni calcoli, otterremo:

!

x = q2 "p2, y = 2pq, z = p2 + q2,

ossia la stessa formula del caso d = 1, però con lo scambio di x ed y.

Riassumendo, abbiamo trovato tutte le terne pitagoriche primitive con la formula

!

x = 2ab, y = a2 " b2, z = a2 + b2, con MCD(a,b) = 1 e z > 0.

Da una di esse, se i tre numeri sono non nulli, se ne ricavano due in N e ben 16 in Z,

scambiando x con y e cambiando i segni dei tre numeri.

NOTA. Le trasformazioni che mutano in sé la formula

!

x2 + y2 = z2 come detto sono 16 e, componendole,

formano un gruppo G d’ordine 16. In particolare, ce ne sono 8 che agiscono solo sul primo membro e

formano un sottogruppo D isomorfo al gruppo

!

D4 del quadrato. Infatti, oltre all’identità

!

" x = x" y = y

# $ %

&1 00 1

'

( )

*

+ ,

abbiamo

!

" x = #x" y = y

$ % &

'#1 00 1

(

) *

+

, - , poi

!

" x = x" y = #y

$ % &

'1 00 #1

(

) *

+

, - ,

!

" x = #x" y = #y

$ % &

'#1 00 #1

(

) *

+

, - ,

!

" x = y" y = x

# $ %

&0 11 0

'

( )

*

+ , ,

!

" x = #y" y = x

$ % &

'0 #11 0

(

) *

+

, - ,

!

" x = y" y = #x

$ % &

'0 1#1 0

(

) *

+

, - ed infine

!

" x = #y" y = #x

$ % &

'0 #1#1 0

(

) *

+

, - (di ciascuna è stata riportata

anche la corrispondente matrice)

Queste sono appunto le 8 isometrie che

trasformano per esempio il quadrato di vertici

(1,1), (1,-1), (-1,-1), (-1,1) in sé. Osserviamo

che D è un sottogruppo normale in G perché

ha metà degli elementi di G.

Le due trasformazioni che riguardano z (identità e cambio di segno) non influiscono su x ed y, quindi il

sottogruppo

!

S " 1,#1{ }, $( ) " S2 (gruppo simmetrico su 2 oggetti) che formano commuta elemento per

elemento con gli 8 elementi di D. Allora, anche S è normale in G, (anzi, è nel centro di G) e quindi

!

G = D " S # D4 " S2.

Infatti, detta M

!

M =m11 m12m21 m22

"

# $

%

& ' la matrice 2x2 della trasformazione sulle incognite x ed y, la matrice

complessiva è allora del tipo

!

m11 m12 0m21 m22 0

0 0 ±1

"

#

$ $ $

%

&

' ' ' .

(*) Se per esempio a è pari, anche u+v è pari quindi anche u-v lo è e dunque anche b è pari, mentre MCD(a,b) = 1.


8

Come noto, una congettura di Fermàt affermava che l’analoga equazione

!

xn + yn = zn , con x, y, z interi

non nulli e n ≥ 3 non ha soluzioni. Lo stesso Fermàt affermò di averne trovato una dimostrazione

meravigliosa, ma troppo lunga per essere contenuta nel bordo di un trattato sui numeri che stava leggendo.

Si sa che egli ricondusse facilmente il problema ai soli esponenti primi: se per p primo dispari è impossibile,

allora per ogni suo multiplo n = p⋅m lo è:

!

xn + yn = zn " xm#

$ %

&

' ( p

+ ym#

$ %

&

' ( p

= zm#

$ %

&

' ( p

. Inoltre, ne dimostrò

l’impossibilità per p = 4. Dopo più di tre secoli di sforzi da parte di molti grandi matematici, alla fine del

millennio scorso l’inglese Wiles riuscì a dimostrare la congettura di Fermàt, e ne uscì anche un film di

successo. Poiché la dimostrazione sembra proprio giusta, gli appassionati sono invitati a cimentarsi con altri

problemi ancora aperti…

C) NUMERI PRIMI. Nella scuola media il primo anno si insegnano i numeri primi,

ossia quegli interi > 1 che hanno due soli divisori. Si insegna poi che con essi si possono

scomporre gli altri numeri interi > 1 ed in un unico modo, se il prodotto è scritto in forma

canonica: per ogni n > 1, allora

!

n = pihi

i=1

r" , con

!

p1 < p2 < K < pr , r ≥ 1 ed

!

hi > 0 "i . La

scomposizione è giustificata con la necessità di ridurre le frazioni ai minimi termini e

quindi semplificare i calcoli nelle espressioni e nelle equazioni. Serve in particolare per il

calcolo dei divisori di un numero e del MCD ed mcm di due numeri.

Per facilitare i calcoli da scuola media, si danno criteri di divisibilità per 2, 3, 5, 11,

relativamente facili da applicare (ma il 7 fa eccezione). Si insegna anche che se si cerca di

scomporre un numero n > 1 e questo non risulta divisibile per i primi che hanno il

quadrato ≤ n, allora è certamente primo.

Una tecnica che si insegna è il crivello di Eratostene per trovare i primi minori di un dato numero, per

esempio 1000. Quest’ultimo merita un po’ d’attenzione: per un certo tempo è stato usato a scuola per

illustrare come idee nuove possano sveltire i programmi per computer volti a costruirsi un elenco di primi.

Per esempio, inizialmente si elencano i numeri da 2 a 1000, poi:

- si trascrive in coda all’elenco dei primi il primo numero della lista e si cancellano tutti i suoi multipli;

- si prosegue fino a che la lista non sia vuota.

Si trova quindi via via un elenco, che si allunga fino a comprendere tutti i primi minori di 1000.

Poi però si cerca di usare la testa: a parte il 2, unico primo pari, si elencano solo i dispari minori di 1000 e si

procede come prima. Tuttavia, poiché i numeri maggiori di 31 hanno il quadrato maggiore di 1000, tutti i

numeri superstiti maggiori di 31 sono primi, ed il programma è assai più rapido.


9

Ecco la lista dei primi 24 numeri primi (nelle seconde righe).

1 2 3 4 5 6 7 8 9 10 11 12

2 3 5 7 11 13 17 19 23 29 31 37

13 14 15 16 17 18 19 20 21 22 23 24 41 43 47 53 59 61 67 71 73 79 83 89

Euclide ha dimostrato che ci sono infiniti numeri primi, pertanto per ogni n ≥ 1 possiamo

chiederci chi sia l’n-esimo numero primo. Sarà possibile dare una funzione esplicita p = f(n)

che associ ad ogni n l’n-esimo numero primo? Già da questo tratto iniziale si vede che non

sembrano esserci regolarità: ci sono primi dispari consecutivi, come 3 e 5, 11 e 13, 71 e 73:

i primi gemelli. Ma ci sono distanze maggiori, anche se in questi esempi sembra che non

possano essere troppo grandi. Eppure, la distanza tra due primi consecutivi non è limitata

superiormente. Per convincercene, ricordiamo che il simbolo n! vale 0 se n = 0 o se n = 1,

mentre se n > 1 è il prodotto dei numeri da 1 ad n. Quindi, se n > 1, n! è multiplo di tutti i

numeri interi positivi e ≤ n.

Allora, tra n!+2 e n!+n non ci sono primi. Infatti, per ogni k, 2 ≤ k ≤ n, il numero k divide n!,

quindi n!+k è multiplo di k e non è primo.

A proposito, il numero n! si scompone nel prodotto dei fattori primi p ≤ n, ma con quale

esponente? Un semplice algoritmo è il seguente: si divide n per p e si considera il quoziente

!

q1. Se è < p, allora nella fattorizzazione di n il primo p ha esponente

!

q1. Altrimenti si

divida

!

q1 per p e si consideri il quoziente

!

q2, e così via, fino ad ottenere un quoziente

minore di p. Allora l’esponente di p è la somma di tutti i quozienti ottenuti. Ovviamente, se

p > n/2, ha esponente 1. Vediamo un esempio con 23!

23 2 23 3 23 5 23 7 23 11 11 2 7 3 4 3 2 5 2 2 4 3 2 2 2 9 1

19 Pertanto,

!

23!= 219 "39 "54 "73 "112 "13 "17 "19 "23

Tornando al discorso di prima, un celebre teorema di Bertrand afferma che per ogni n ≥ 1,

tra n e 2n esiste almeno un numero primo.

Insomma, chi è il millesimo numero primo? Chi è il miliardesimo numero primo?

Con pazienza, un buon computer ed il software adeguato, che non facciano errori,

comunque col crivello di Eratostene si riesce a trovare la risposta, se c’è abbastanza tempo

(non più di 5 miliardi di anni, la vita residua del sole…).


10

Un problema che ha un certo interesse per gli informatici, soprattutto come test per i nuovi

computer è trovare numeri primi sempre più grandi. I primi cercati sono dispari della

forma

!

2n "1. Quali di essi possono essere primi?

Un metodo per scomporre numeri espressi come valore di espressioni aritmetiche è quello di scomporre la

successione con le tecniche dei prodotti notevoli. Se n non è primo si può scrivere nella forma

!

n = p "q , con

p primo, quindi, ricordando la nota formula algebrica

!

xp "1 = x "1( ) # xk

k=0

p"1

$ e posto

!

x = 2q , si ricava la

fattorizzazione:

!

2n "1 = 2q#

$ %

&

' ( p"1 = 2q "1#

$ %

&

' ( ) 2q#

$ %

&

' ( k

k=0

p"1

*

Allora se

!

2n "1 è primo, deve essere q = 1 e quindi l’esponente n deve essere un primo p.

Ma

!

2p "1 sarà sempre primo? Se p = 2 sì. Da qui in poi serve un software che sia in grado di verificare se

un dato numero naturale dispari x > 1 sia primo o no, oppure tanta pazienza ed abilità nello svolgere

montagne di calcoli senza sbagliarsi.

Si vede subito che per x = 11, che è primo, si ha:

!

211 "1 = 23 #89

I numeri della forma

!

2p "1 che sono primi sono detti primi di Mersenne. Non si sa se ce ne siano

infiniti o no, ma se ne conoscono con migliaia di cifre. Uno di essi è finito anche sulle magliette (le

cosiddette T-shirts), qualche anno fa.

Un problema simile riguarda i numeri della forma

!

2n +1: con la stessa tecnica, se n è multiplo di un

primo dispari p, possiamo scrivere

!

n = p "q e quindi, come sopra,

!

2n +1 = 2q"

# $

%

& ' p

+1 = 2q +1"

# $

%

& ' ( )2q"

# $

%

& ' k

k=0

p)1

*

Pertanto, un numero di questo tipo può essere primo solo se n è una potenza di 2. I primi

della forma

!

22k+1 sono detti primi di Fermàt. Sono importanti perché si dimostra che un

poligono regolare con un numero primo p di lati si costruisce con riga e compasso se e solo

se p è un primo di Fermàt. Vediamo la tabella:

k 0 1 2 3 4 5 6

!

22k+1 3 5 17 257 65.537 4.294.967.297 18.446.744.073.709.551.617

è primo? sì sì sì sì sì = 641×6.700.417 =274.177×67.280.421.310.721


11

Gauss diede una costruzione del poligono di 17 lati e qualcuno lo ha fatto con quello di

257. Non credo che ci si sia riusciti con quello di 65.537.

Torniamo al problema che ha assillato i grandi matematici dell’800, Gauss per

primo: stabilire qualche tipo di regolarità per la successione dei numeri primi. Questo

problema sarà trattato nell’altro modulo del corso. Anticipo qui alcuni risultati e curiosità.

Vari matematici, tra cui P. Mengoli ed I. Newton indipendentemente provarono che

!

1n

n=1

"

# = +", mentre Eulero dimostrò che

!

1

n2n=1

"

# =$2

6. Ricordiamo poi che

!

1n!

n=0

"

# = e $ 2,71.

Questo perché i quadrati ed i fattoriali hanno bassa “densità” entro i numeri naturali.

Invece, sorprendentemente,

!

1p

p primo

"

# = +", perciò i primi hanno grande densità entro N.

Per ogni numero naturale n ≥ 1 calcoliamo i valori della funzione:

π(n) = numero dei primi p ≤ n,

Seguendo un’intuizione di Gauss, confrontiamo i due numeri π(n) e n/ln(n).

Incominciamo con una tabella calcolata con l’ausilio di software appositi:

n 1 2 3 4 5 6 7 8 9 10 π(n) 0 1 2 2 3 3 4 4 4 4 ln(n) 0,000 0,693 1,099 1,386 1,609 1,792 1,946 2,079 2,197 2,303

!

! n( ) " ln n( )n

0,000 0,347 0,732 0,693 0,966 0,896 1,112 1,040 0,977 0,921

Per trovare altri valori della successione π(n) ci serve una lista di primi abbastanza estesa e una paziente

tabulazione, oppure la possibilità di scrivere un programma in un qualche linguaggio di programmazione.

Un semplice algoritmo ricorsivo per il calcolo della successione π(n) è il seguente:

• π(1) = 0

• Per ogni n > 1, se n è primo allora π(n) = π(n-1)+1; altrimenti, π(n) = π(n-1)

Dopo ciò, si divide (in forma approssimata) π(n) per il quoziente n/ln(n) e si ottiene una successione di

numeri decimali, che pur oscillando su e giù, per n tendente all’infinito tende ad 1.

I valori della successione π(n), 1 ≤ n ≤ 1001, sono riportati in una colonna di Excel, poi moltiplicati

per ln(n) e divisi per n. Il risultato è mostrato nel grafico ad istogramma riportato nella figura seguente.

Si osservi come la discesa ad 1 sia assai lenta. Per n =1000 e per n = 100.000 si ha infatti:

π(1000) = 168 ⇒

!

" 1000( ) # ln 1000( )1000

$ 1,1605 ; π(100.000) = 9.592 ⇒

!

" 100.000( ) # ln 100.000( )100.000

$ 1,10432.


12

0,0

0,2

0,4

0,6

0,8

1,0

1,2

1,4

1 101 201 301 401 501 601 701 801 901 1001

Un problema divertente è trovare polinomi su N che diano solo numeri primi,

almeno per valori piccoli di n. Per esempio, sia dato il polinomio

!

f n( ) = n2 "n + 41. Se ne

calcolino alcuni valori; che cos’hanno di particolare?

Con l’ausilio di un software calcoliamo i valori e scriviamo true se f(n) è primo, false in caso contrario. La

sorpresa è che per n ≤ 40 si trovano solo numeri primi. Per n = 41 si ha

!

f 41( ) = 1.681 = 412.

n 1 2 3 4 5 6 7 8 9 10 11 12 f(n) 41 43 47 53 61 71 83 97 113 131 151 173

isprime(n) true true true true true true true true true true true true

n 13 14 15 16 17 18 19 20 21 22 23 24 f(n) 197 223 251 281 313 347 383 421 461 503 547 593


n 25 26 27 28 29 30 31 32 33 34 35 36 f(n) 641 691 743 797 853 911 971 1033 1097 1163 1231 1301


n 37 38 39 40 41 42 43 44 45 46 47 48 f(n) 1373 1447 1523 1601 1681 1763 1847 1933 2021 2111 2203 2297

isprime(n) true true true true false false true true false true true true

Concludiamo questa rassegna cercando se si possa scomporre 100 nella somma di due primi.

Naturalmente si può supporre 100 = p+q, con p ≤ q, quindi con p ≤ 47.

La lista dei primi p ≤ 47 e la verifica se 100-p sia primo o no si può eseguire manualmente.

p 3 5 7 11 13 17 19 23 29 31 37 41 43 47 q 97 95 93 89 87 83 81 77 71 69 63 59 57 53 true false false true false true false false true false false true false true

Dunque, il 100 si scrive in 6 modi diversi come somma di due primi. La congettura di Goldbach presume

che ogni numero pari > 2 sia somma di due primi.

Una analoga congettura di Polignac, profondamente diversa perché non verificabile neppure nei casi

particolari, afferma che ogni numero pari è differenza di due primi addirittura in infiniti modi.


13

La differenza tra le due congetture è ovvia: dato il numero pari n = 2m, gli eventuali due primi p e q tali che

p−q = n potrebbero essere così grandi da non essere trovati mai; non solo, ma il non riuscire a trovarli non

smentirebbe questa congettura, mentre smentirebbe quella di Goldbach, in cui gli addendi sono minori di n.

Sui numeri primi, oltre alla loro distribuzione nella successione dei numeri naturali e

alla congettura di Goldbach e Polignac ci sono tantissimi risultati e numerosi problemi

aperti.

Dirichlét (1837) dimostrò che in ogni progressione aritmetica

!

an = a0 + n "d , se

!

MCD a0,d( ) = 1 allora ci sono infiniti termini che sono primi.

A proposito di progressioni aritmetiche, un profondissimo e sorprendente risultato

di questi anni è il seguente: (Green, Tao, 2003): nella successione dei primi esistono

sequenze di termini in progressione aritmetica di lunghezza arbitraria.

Un esempio? Ecco 25 numeri primi in progressione aritmetica, trovati nel 2008 (credeteci

sulla parola che sono proprio tutti primi, oppure verificatelo direttamente!):

6.171.054.912.832.631 + 336.384 ⋅ 223.092.870 ⋅ k, 0 ≤ k ≤ 24

Termino citando un risultato ottocentesco di Zsigmondy, utile nello studio dei gruppi finiti

aventi per ordine la potenza di un primo: con alcune eccezioni, per ogni primo p e per ogni

n ≥ 2, esiste almeno un primo q che divide

!

pn "1p "1

, ma non divide né p-1 né

!

pk "1p "1

, per

ogni k < n. Le sole eccezioni sono p = 2 ed n = 6, oppure p primo di Mersenne ed n = 2.

Vediamo alcuni casi per p = 3, che è di Mersenne: per n = 2 non ci sono primi “nuovi”.

n 2 3 4 5 6 7 8 9 10

!

3n "12

!

22

!

13

!

23 "5

!

112

!

22 "7 "13

!

1093

!

24 "5 "41

!

13 "757

!

22 "112 "61

D) IL TRIANGOLO ARITMETICO ED I NUMERI DI FIBONACCI. Siano X un

insieme non vuoto, n0∈N ed M = {n∈N | n ≥ n0}. Chiamiamo successione in X ogni funzione

f:M→X. In particolare, se M = N, posto an = f(n), la successione si denota anche con

!

an( )n"N.

Una successione f: N→X si può definire esplicitamente, assegnando ad ogni n∈N il

valore f(n), ma anche ricorsivamente, assegnando le condizioni iniziali f(0), ..., f(h-1) e

facendo dipendere f(n+h) da f(n), f(n+1), ...., f(n+h-1).


14

Nel seguito sarà X = R, campo dei numeri reali, di cui N è pensato come sottoinsieme,

ed n0 = 0 oppure n0 = 1. Nel costruire le tabelle si è fatto uso di Excel, il cui riempimento

automatico è perfetto per le definizioni ricorsive. Vediamo due esempi:

a) Il fattoriale n! dipende da un solo valore iniziale:

!

0!= 1n +1( )!= n!" n +1( )

# $ %

& % ⇒

!

n 0 1 2 3 4 5 6n! 1 1 2 6 24 120 720

…

b) I numeri di Fibonacci sono una successione che dipende da due valori iniziali:

!

a0 = 1a1 = 1an+2 = an + an+1

"

# $

% $

⇒

!

n 0 1 2 3 4 5 6 7an 1 1 2 3 5 8 13 21

…

In alcuni testi si pone

!

a0 = 0, ma più frequentemente si parte da 1. In tal modo è possibile

definire il quoziente fra due termini consecutivi in ogni caso:

!

an+1an

, n " 0.

Questa successione di quozienti è interessante, perché ha limite finito. Per calcolarlo, il

trucco usato da Eulero è il seguente: posto

!

l = limx"#

an+1an

, che è positivo, si ha anche:

!

l = limx"#

an+2an+1

= limx"#

an+1 + anan+1

= limx"#

1+an

an+1

$

% & &

'

( ) ) = lim

x"#1+

1an+1an

$

%

& & & &

'

(

) ) ) )

= 1+1l

.

Ne segue

!

l2 " l "1 = 0, la cui unica soluzione positiva è

!

l =1+ 5

2, cioè il numero aureo γ

degli antichi greci, rapporto tra base ed altezza di un rettangolo dal quale si può ritagliare

un quadrato di lato l’altezza, ottenendo un rettangolo simile a quello iniziale. Inoltre,

poiché

!

2 " sin 2#20

$

% & &

'

( ) ) =

5 *12

=1+

, ne viene che il rapporto fra il raggio di una circonferenza ed

il lato del decagono regolare inscritto è proprio γ. Poiché il rapporto aureo si può costruire

con riga e compasso, allora anche il lato del decagono e quello del pentagono inscritti in un

cerchio di dato raggio si possono agevolmente costruire con riga e compasso.

I coefficienti binomiali sono una famiglia di successioni

!

Cn,k dipendenti da un

parametro naturale k. Si possono introdurre in molti modi, ma quello che preferisco è

basato sugli anagrammi di una parola. Se le lettere sono n e sono distinte, allora ci sono n!


15

anagrammi. Se le lettere distinte sono r e le loro frequenze sono

!

k1,K, kr , con

!

kii=1

r" = n ,

allora è immediato osservare che le permutazioni di una stessa lettera non cambiano la

parola, quindi si hanno solo

!

n!k1!"k2!Lkr !

anagrammi distinti. Se le lettere distinte sono solo

due, come nella parola MAMMA, detta k la frequenza della prima lettera, quella della

seconda è n-k, quindi abbiamo

!

Cn,k =n!

k!" n # k( )! anagrammi.

Poiché n! è multiplo di (n-k)!, possiamo allora scrivere

!

Cn,k nella forma

!

n " n #1( )K n # k #1( )( )k!

, che possiamo reinterpretare come polinomio di grado k nella

variabile naturale n. Esso ha come radici tutti i numeri n < k, ossia

!

Cn,k = 0 se

!

k > n .

Questi numeri sono anche detti coefficienti binomiali, e denotati col simbolo

!

nk

"

# $ $ %

& ' ' =

n!k!( n ) k( )!

, perché compaiono nello sviluppo della potenza n-esima del binomio x+y

secondo la nota formula di Newton.

Al variare di n e k ≥ 0 i coefficienti binomiali costituiscono una specie di matrice ad

infinite righe e colonne, numerate da 0 in poi. Le proprietà di questa matrice sono ben

note:

- Tutti gli elementi sono numeri naturali.

- La colonna contrassegnata da k = 0 ha tutti gli elementi uguali ad 1.

- Per ogni n, k si ha

!

n +1k +1

"

# $ $

%

& ' ' =

nk

"

# $ $ %

& ' ' +

nk +1

"

# $ $

%

& ' ' (formula di Stiefel)

- La somma dei termini della n-esima riga è

!

2n

!

n \ k 0 1 2 3 4 5 6 7 2n

0 1 1 = 20

1 1 1 2 = 21

2 1 2 1 4 = 22

3 1 3 3 1 8 = 23

4 1 4 6 4 1 16 = 24

5 1 5 10 10 5 1 32 = 25

6 1 6 15 20 15 6 1 64 = 26

7 1 7 21 35 35 21 7 1 128 = 27


16

Nella tabella è mostrato il minore iniziale d’ordine 8 (con n e k da 0 a 7): per semplicità, i

termini nulli li ho omessi.

Che cosa c’entra coi numeri di Fibonacci questo antichissimo “triangolo”, attribuito

da noi a Tartaglia, in Francia a Pascal, in Germania a Stiefel, ma noto ai matematici indiani

molti secoli prima di costoro?

Se proviamo a sommare i termini sulle linee parallele alla diagonale principale,

otteniamo sempre

!

+" oppure 0.

Se invece consideriamo i termini paralleli alla diagonale secondaria, abbiamo un

numero finito di addendi non nulli e la loro somma è finita. Nella prossima illustrazione, ho

evidenziato nel primo minore d’ordine 13, le caselle delle linee parallele alla diagonale

secondaria con lo stesso colore, alternativamente giallo e verde: la loro somma è sulla

sinistra, in rosso, in una casella con lo stesso colore. Le somme sono:

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233

Si tratta proprio dei numeri di Fibonacci.

i

!

Fi 0 1 2 3 4 5 6 7 8 9 10 11 12 1 0 0 0 0 0 0 0 0 0 0 0 0

0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 1 1 1 2 1 0 0 0 0 0 0 0 0 0 0 2 2 1 3 3 1 0 0 0 0 0 0 0 0 0 3 3 1 4 6 4 1 0 0 0 0 0 0 0 0 4 5 1 5 10 10 5 1 0 0 0 0 0 0 0 5 8 1 6 15 20 15 6 1 0 0 0 0 0 0 6 13 1 7 21 35 35 21 7 1 0 0 0 0 0 7 21 1 8 28 56 70 56 28 8 1 0 0 0 0 8 34 1 9 36 84 126 126 84 36 9 1 0 0 0 9 55 1 10 45 120 210 252 210 120 45 10 1 0 0

10 89 1 11 55 165 330 462 462 330 165 55 11 1 0 11 144 1 12 66 220 495 792 924 792 495 220 66 12 1 12 233 1 13 78 286 715 1287 1716 1716 1287 715 286 78 13

Ossia, detto

!

Fn l’n-esimo numero di Fibonacci, si ha

!

Fn =n " k

k

#

$ % %

&

' ( (

k)0* .

Questa non è l’unica sorpresa di questo triangolo, e non è l’unico modo di scriverlo,

perché spesso si rappresenta in forma di triangolo isoscele, ed allora se ne apprezza la

simmetria, ma non solo: anche i numeri sul suo asse di simmetria sono importanti in

Combinatoria Algebrica.

MODULO PROF. VERARDI - unibo.itverardi/T d N Verardi, Introduzione.pdf · Riprenderemo questo...

Documents

Transcript of MODULO PROF. VERARDI - unibo.itverardi/T d N Verardi, Introduzione.pdf · Riprenderemo questo...