Teoria dei numeri I 2013-14, modulo prof. Verardi – Introduzione
TEORIA DEI NUMERI I
MODULO PROF. V ERA RDI
Pr er eq ui sit i o bbli gat ori : 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.
NOT A. 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.
1
Teoria dei numeri I 2013-14, modulo prof. Verardi – Introduzione
INTRODUZIONE
A)
S OL UZI ONI
I NT ER E
NON
NE G AT I VE.
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?.
2
Teoria dei numeri I 2013-14, modulo prof. Verardi – Introduzione
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:
!9t + 9 " #3n # 7t = n
7 " 4n +
(
)
(
)
! #
x = 4n + 9t
3n
Ossia, $
. Per rendere y ≥ 0, occorre prendere t in modo che sia t " #
. Affinché
7
% y = "3n " 7t
!
sia x ≥ 0, occorre invece t " #
!
"
"
!
"
!
4n
9
#t#"
28n
63
3n
7
#t#"
4n
. Quindi, in definitiva deve esistere un intero t tale che
9
!
. Si possono anche ridurre allo stesso denominatore le due frazioni:
27n
63
!
.
Allora
è
chiaro
che
se
n
=
63+h,
con
h
positivo,
allora
27n # 28n & n
h
4n
3n
" %%"
= 1+
> 1, quindi un intero t tra quelle due frazioni "
(( =
#t#"
63 $ 63 ' 63
63
9
7
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) ANG OLI RE TTI E TER NE P ITAG ORI CHE . 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.
3
Teoria dei numeri I 2013-14, modulo prof. Verardi – Introduzione
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.
4
Teoria dei numeri I 2013-14, modulo prof. Verardi – Introduzione
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
x 2 + y 2 = 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$k 2 + k + h 2 + 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 X 2 + Y 2 = 1. Sia A = 0, "1
(
)
un punto della circonferenza. Le rette passanti per
! Y hanno equazione Y = mX " 1 .
A e diverse dall’asse
!
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
!
5
Teoria dei numeri I 2013-14, modulo prof. Verardi – Introduzione
$
&
& Y = mX " 1
#
Risolviamo il sistema: % 2
2
&X + Y = 1
&
'
$
2m
&X =
&
m2 +1
%
. Si ricava quindi che, viceversa, se m è
m2 "1
&
&Y = 2
'
m +1
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).
#
#
2ab
2ab
(z
%X =
%x =
%
%
a 2 + b2
a 2 + b2
'$
Allora, sostituendo, si ottiene: $
. Allora poniamo z = a 2 + b2 e
2
2
2
2
a "b
a "b
%
%
(z
%Y = 2
%y = 2
2
&
&
a +b
a + b2
!
quindi avremo x = 2ab, y = a 2 " b2, z = a 2 + b2.
!
Adesso è facile verificare che questa terna soddisfa la condizione x2 + y2 = z2 .
! anche se a = 0 oppure se b = 0, o se x ed y sono interi negativi.
La verifica
Ma avremo trovato terne primitive? Le avremo trovate tutte?
!
Sicuramente mancano quelle con z < 0, ma non è un grosso guaio: basta prendere
#
&
z = t " %a 2 + 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
#
&
t " %a 2 + b2 (
$
'
che la terna sia primitiva, si dovrà prendere z =
, t = ±1 .
d
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 = a 2 " b2, z = a 2 + b2.
Se d > 1, esistono due interi u, v coprimi e tali che a 2 + b2 = d " u , a 2 " b2 = d # v . Se ne
!
ricava: 2a 2 = d " u + v , 2b2 = d " u # v . Per quanto detto su a 2 e b2 , d non può dividere
(
)
(
)
!
!
entrambi, quindi deve dividere 2, ed allora d = 1 oppure d = 2.
!
!
!
6
!
Teoria dei numeri I 2013-14, modulo prof. Verardi – Introduzione
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 = q 2 " p2, y = 2pq, z = p2 + q 2 ,
!
!
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 = a 2 " b2, z = a 2 + 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
#
'
*
! D 4 del quadrato. Infatti, oltre all’identità $ x" = x & )1 0,
formano un sottogruppo D isomorfo al gruppo
(0 1+
% y" = y
$ x" = #x
(#1 0 +
# x" = y
'0 1*
'*
&)
%
$
-,
,,
) 0 #1,
(1 0+
& y" = #y
% y" = x
!
$ x" = #y
(0 #1+ $ x" = y
( 0 1+
$ x" = #y
( 0 #1+
'*
'*
'*
%
-, %
- ed infine %
- (di ciascuna è stata riportata
)1 0 , & y" = #x
)#1 0,
)#1 0 ,
& y" = x
& y" = #x
!
!
!
!
anche la corrispondente matrice)
abbiamo
!
$ x" = #x
(#1 0+
'*
%
-,
) 0 1,
& y" = y
!
poi
$ x" = x
(1 0 +
'*
%
-,
! & y" = #y
)0 #1,
!
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 # D 4 " S2 .
!
"m
m 12 %
Infatti, detta M M = $ 11
' la matrice 2x2 della trasformazione sulle incognite x ed y, la matrice
#m 21 m 22&
"m
m 12 0 %
$ 11
'
complessiva è allora del tipo $m 21 m 22 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.
!
7
Teoria dei numeri I 2013-14, modulo prof. Verardi – Introduzione
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,
#
&p #
&p #
&p
allora per ogni suo multiplo n = p⋅m lo è: xn + yn = zn " % xm ( + % ym ( = %zm ( . 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) NUME RI PRI MI. 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
r
canonica: per ogni n > 1, allora n =
" p ih
i
, con p1 < p2 < K < p r , r ≥ 1 ed h i > 0 "i . La
i=1
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.
8
Teoria dei numeri I 2013-14, modulo prof. Verardi – Introduzione
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 q 2 , 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
11
5
2
1
19
2
2
2
2
23
7
2
9
3
3
23
4
4
5
23
3
3
7
23
2
2
11
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…).
9
Teoria dei numeri I 2013-14, modulo prof. Verardi – Introduzione
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 x p " 1 = x " 1 #
p"1
) $ xk
(
k=0
fattorizzazione:
p"1
# !&p
#
&
# q &k
2n " 1 = %2q ( " 1 = %2q " 1( )
%2 (
$
'
$
*$
'
k=0
e posto x = 2q , si ricava la
!
!
'
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
! dato numero naturale dispari x > 1 sia primo o no, oppure tanta pazienza ed abilità nello svolgere
un
!
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,
!
!
" %p
"
%
2n + 1 = $2q ' + 1 = $2q + 1' (
#
&
#
&
p)1
"
%k
* $#)2q '&
k=0
Pertanto, un numero di questo tipo può essere primo solo se n è una potenza di 2. I primi
k
!
della forma 22 + 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
22 + 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
k
!
10
Teoria dei numeri I 2013-14, modulo prof. Verardi – Introduzione
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
"
#
1
= +" , mentre Eulero dimostrò che
n
n=1
"
#
1
2
n=1n
=
$2
. Ricordiamo poi che
6
"
1
= e $ 2,71 .
# n!
n=0
Questo perché i quadrati ed i fattoriali hanno bassa “densità” entro i numeri naturali.
!
"!
#
Invece, sorprendentemente,
p primo
!
1
= +" , perciò i primi hanno grande densità entro N.
p
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
π(n)
ln(n)
1
0
0,000
2
1
0,693
3
2
1,099
4
2
1,386
5
3
1,609
6
3
1,792
7
4
1,946
8
4
2,079
9
4
2,197
10
4
2,303
() ()
0,000
0,347
0,732
0,693
0,966
0,896
1,112
1,040
0,977
0,921
! n " ln n
n
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 ⇒
(
) (
) $ 1,1605 ; π(100.000) = 9.592 ⇒ "(100.000) # ln(100.000) $ 1,10432 .
" 1000 # ln 1000
1000
100.000
!
!
11
Teoria dei numeri I 2013-14, modulo prof. Verardi – Introduzione
1,4
1,2
1,0
0,8
0,6
0,4
0,2
0,0
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 = n 2 " 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
f(n)
isprime(n)
1
41
true
2
43
true
3
47
true
4
53
true
5
61
true
6
71
true
7
83
!
true
8
97
true
9
113
true
10
131
true
11
151
true
12
173
true
n
f(n)
isprime(n)
13
197
true
14
223
true
15
251
true
16
281
true
17
313
true
18
347
true
19
383
true
20
421
true
21
461
true
22
503
true
23
547
true
24
593
true
n
f(n)
isprime(n)
25
641
true
26
691
true
27
743
true
28
797
true
29
853
true
30
911
true
31
971
true
32
1033
true
33
1097
true
34
1163
true
35
1231
true
36
1301
true
n
f(n)
isprime(n)
37
1373
true
38
1447
true
39
1523
true
40
1601
true
41
1681
false
42
1763
false
43
1847
true
44
1933
true
45
2021
false
46
2111
true
47
2203
true
48
2297
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
q
3
97
true
5
95
false
7
93
false
11
89
true
13
87
false
17
83
true
19
81
false
23
77
false
29
71
true
31
69
false
37
63
false
41
59
true
43
57
false
47
53
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.
12
Teoria dei numeri I 2013-14, modulo prof. Verardi – Introduzione
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 a n = a 0 + n " d , se
(
)
MCD a 0 , 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 " 1
pk " 1
, ma non divide né p-1 né
, per
p "1
p "1
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
3n " 1
2
22
!
!
3
13
!
4
5
6
23 " 5
11 2
22 "7 "13
!
!
7
!
1093
!
8
9
24 "5 " 41
13 "757
!
!
10
22 "112 " 61
D) I L TR I ANG OL O ARI T ME TI CO ED I NUMERI DI FIB ONACCI. 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
(a n )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).
13
Teoria dei numeri I 2013-14, modulo prof. Verardi – Introduzione
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!= 1
n 0 1 2 3 4
5
6
⇒
…
$
n! 1 1 2 6 24 120 720
%& n + 1 != n!" n + 1
(
)
(
)
b) I numeri di Fibonacci sono una successione che dipende da due valori iniziali:
!
!
"a = 1
$ 0
n 0 1 2 3 4 5 6 7
⇒
…
#a1 = 1
a n 1 1 2 3 5 8 13 21
$a
% n +2 = a n + a n +1
In alcuni testi si pone a 0 = 0 , ma più frequentemente si parte da 1. In tal modo è possibile
!
!
a
definire il quoziente fra due termini consecutivi in ogni caso: n +1 , n " 0 .
an
!
Questa successione di quozienti è interessante, perché ha limite finito. Per calcolarlo, il
trucco usato da Eulero è il seguente: posto l = lim
a n +1
!
x"# a n
, che è positivo, si ha anche:
$
'
&
)
$
'
a
a
+ an
a
1 )
1
!
l = lim n +2 = lim n +1
= lim &&1 + n )) = lim &1 +
= 1+ .
&
)
a n +1
a n +1 ( x"#
a n +1
l
x"# a n +1
x"#
x"#%
&
)
a
%
n (
1+ 5
Ne segue l2 " l " 1 = 0 , la cui unica soluzione positiva è l =
, cioè il numero aureo γ
2
!
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,
!
$ 2# '
poiché 2 " sin&&
)) =
% 20 (
5 *1 1
= , ne viene che il rapporto fra il raggio di una circonferenza ed
2
+
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!
14
Teoria dei numeri I 2013-14, modulo prof. Verardi – Introduzione
r
anagrammi. Se le lettere distinte sono r e le loro frequenze sono k1,K, k r , con
"ki = n,
i=1
allora è immediato osservare che le permutazioni di una stessa lettera non cambiano la
!
n!
!
parola, quindi si hanno solo
anagrammi distinti. Se le lettere distinte
sono solo
k1!"k 2!Lk r !
due, come nella parola MAMMA, detta k la frequenza della prima lettera, quella della
seconda è n-k, quindi!abbiamo Cn,k =
Poiché n!
(
è
) ( (
)) ,
n " n #1 K n # k #1
k!
multiplo
di
n!
(
)
k!" n # k !
(n-k)!,
anagrammi.
possiamo
allora scrivere
Cn,k
nella
forma
!
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
!
!
"n %
n!
!
, perché compaiono nello sviluppo della potenza n-esima del binomio x+y
$$ '' =
#k & k!( n ) k !
(
)
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.
-
"n + 1%
'' =
Per ogni n, k si ha $$
#k + 1&
-
La somma dei termini della n-esima riga è 2n
"n % " n %
$$ '' + $$
'' (formula di Stiefel)
#k & #k + 1&
!
n\k 0 1 2
0
1
3!
4
5
6 7
2n
1 = 20
1
1 1
2 = 21
2
1 2 1
4 = 22
3
1 3 3
1
4
1 4 6
4
5
1 5 10 10 5
6
1 6 15 20 15 6
7
1 7 21 35 35 21 7 1 128 = 27
8 = 23
16 = 24
1
!
15
32 = 25
1
1
64 = 26
Teoria dei numeri I 2013-14, modulo prof. Verardi – Introduzione
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
1
1
2
2
3
3
4
5
5
8
6 13
7 21
8 34
9 55
10 89
11 144
12 233
0
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
0
1
2
3
4
5
6
7
8
9
10
11
12
13
2
0
0
1
3
6
10
15
21
28
36
45
55
66
78
3
0
0
0
1
4
10
20
35
56
84
120
165
220
286
4
5
6
7
8
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
5
1
0
0
0
15
6
1
0
0
35
21
7
1
0
70
56
28
8
1
126 126
84
36
9
210 252 210 120
45
330 462 462 330 165
495 792 924 792 495
715 1287 1716 1716 1287
9
0
0
0
0
0
0
0
0
0
1
10
55
220
715
#
&
Ossia, detto Fn l’n-esimo numero di Fibonacci, si ha Fn =
10
0
0
0
0
0
0
0
0
0
0
1
11
66
286
11
0
0
0
0
0
0
0
0
0
0
0
1
12
78
12
0
0
0
0
0
0
0
0
0
0
0
0
1
13
* %%$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.
16
© Copyright 2024 ExpyDoc
