Funzioni sui numeri interi, curiosità  e applicazioni

NUMERI FIDANZATI

Infine, applicando la stessa regola dei numeri amichevoli ma non considerando l’1 nella somma dei

divisori, si ottengono i “numeri fidanzati”.

In simboli, due numeri a e b sono fidanzati se e

a = s (b) – 1 b = s (a) – 1.

Questo curioso nome si deve al fatto che Pitagora distingueva i numeri pari come femminili e i

dispari come maschili, e per l’appunto due numeri fidanzati sono sempre uno pari e l'altro dispari.

Al contrario, le coppie di numeri amichevoli e le catene di numeri socievoli sono sempre formate da

numeri o tutti pari o tutti dispari. Ricordate il film “Harry ti presento Sally”? Sembra che anche in

matematica venga sancita l’impossibilità di un’amicizia tra esseri (in questa caso numeri) di sesso

maschile e di sesso femminile!

La prima coppia di fidanzati è formata dai numeri 48 e 75, detti anche "promessi sposi".

1.4 - Funzione φ (n). Numero di interi minori di n coprimi con n

Questa funzione - uno degli innumerevoli contributi alla scienza del grande matematico svizzero del

‘700 Leonhard Euler - ha una grandissima importanza pratica, poiché è alla base dei principali

sistemi di crittografia oggi utilizzati.

Ma procediamo con ordine, partendo dalla considerazione che per ogni numero primo n, tutti gli

interi minori di n sono coprimi con esso; dunque, per qualsiasi numero primo φ(n) = n – 1.

Inoltre, si può facilmente verificare che se n = pq (con p e q numeri primi), φ(n) = (p – 1)(q – 1).

Utilizzando l’aritmetica modulare, si ha il Teorema, anch’esso di Eulero, per cui se a ed n sono

φ(n)

coprimi, vale la seguente relazione: ≡ 1 (mod n).

a 5

Su questi presupposti si fonda l’algoritmo di cifratura RSA , il più utilizzato ai giorni nostri per

proteggere codici che devono rimanere segreti, ad esempio i numeri delle carte bancarie. Tale

algoritmo si basa sulle formule appena viste (sempre nel campo dell’aritmetica modulare) e prevede

6

l’utilizzo di 3 grandi numeri n, p, q con n = pq.

4 La precisazione che siano dispari è necessaria per il caso n=2, da cui si ottengono i numeri p=2; q=5; r=17 (primi, ma

non tutti dispari), che danno origine alla coppia, “non amichevole”, 20 - 34.

5 L’algoritmo RSA (dal nome dei suoi inventori Rivers, Shamir e Adleman) è stato elaborato negli anni ’70.

6 Si è ritenuto di dare solo alcuni cenni - necessariamente un po’ frammentari - sulla questione della cifratura dei dati;

per maggiori dettagli si rimanda all’articolo “Dai numeri primi alla crittografia” pubblicato su questo stesso sito (vedi

bibliografia). L’articolo tratta approfonditamente il tema e spiega con estrema chiarezza il funzionamento

dell’algoritmo RSA. 3

www.matematicamente.it Funzioni sui numeri interi di Stefano Borgogni

La difficoltà per chi volesse violare il codice segreto è quella di scomporre in fattori n, ossia trovare

i suoi due unici divisori p e q. Può sembrare a prima vista un problema banale, ma basta scegliere i

numeri p e q sufficientemente grandi affinché anche il più potente elaboratore abbia bisogno di anni

e anni di lavoro per trovare la soluzione!

Oggi si utilizzano a questo scopo numeri di qualche centinaio di cifre, ma l’infinità dei numeri

7

primi (già dimostrata da Euclide) garantisce di poter sempre trovare numeri tali da rendere inutile

qualsiasi progresso nella velocità e nella potenza dei computer. Almeno finché non si scoprirà un

altro metodo per la scomposizione di un numero in fattori…

1.5 - Funzione π (n). Numero dei primi non superiori ad n

Com’è noto, uno dei grandi problemi irrisolti legati ai numeri primi è quello di capire in che modo

si susseguono; generazioni di matematici hanno cercato, finora invano, di capire se esista una regola

nell’infinita successione di questi numeri. Un primo passo in questa direzione è l’elaborazione di

una formula che fornisca, con la massima precisione possibile, il numero di primi minori di un dato

numero n. Questa è, per l’appunto, la funzione π (n).

Tra i matematici che si sono occupati di questa questione, vi è Carl Friedrich Gauss, il “principe dei

matematici”, a cui si deve una stima assai precisa di π (n), legata al logaritmo naturale. La formula

∼

è: cioè al crescere di n il valore di π (n) tende ad avvicinarsi sempre più a n / log n.

π (n) n / log n,

La dimostrazione di questa formula, che è di molto successiva all’epoca dello stesso Gauss, fu

ζ

facilitata dagli studi del matematico tedesco Bernard Riemann, celebre per la sua funzione (s) -

x x x

ζ + 1 / 2 + 1 / 3 + … - e per la

estensione al campo complesso della funzione di Eulero (x) = 1 / 1

ζ

sua ipotesi: Tutte le soluzioni non banali della funzione (s) hanno parte reale pari a 1/2.

Allo stesso Riemann si deve una formula che mostra la dipendenza della funzione π (n) dagli zeri

8

ζ.

della funzione ζ

Infine, segnaliamo che vi è uno stretto legame tra la funzione di Riemann e le funzioni τ (n) e s

(n), ma il dettaglio di queste relazioni esula dall’ambito del presente testo.

2 - TIPOLOGIE DI NUMERI INTERI

Vale la pena di aggiungere ancora qualche considerazione su alcune tipologie di numeri interi che si

possono definire in base alle funzioni appena esaminate, cioè riguardo al loro rapporto con il

numero dei propri divisori o con la somma di essi.

Per non appesantire troppo il presente testo, ci limiteremo a qualche cenno sull’argomento,

rimandando a testi più specifici chi volesse saperne di più.

Lasciando da parte i ben noti numeri primi, le tipologie di numeri interi da considerare sono le

seguenti.

Numeri difettivi

Si tratta dei numeri maggiori della somma dei propri divisori. In altre parole, un numero n è

difettivo se n > s (n).

E’ facile verificare che tutti i numeri primi e le loro potenze sono numeri difettivi. Inoltre, tutti i

divisori propri dei numeri difettivi e dei numeri perfetti sono a loro volta difettivi.

Esempi di numeri difettivi sono 9, 17, 26, 76, 133.

Numeri abbondanti

Al contrario di quanto appena visto, i numeri abbondanti sono quelli inferiori alla somma dei propri

divisori, cioè i numeri per cui vale la relazione n < s (n).

7 Euclide provò che i numeri primi sono infiniti grazie a una dimostrazione per assurdo - semplice e geniale al tempo

stesso - rimasta famosa nella storia della matematica. Si può vedere in proposito l’articolo appena citato.

8 L’ipotesi di Riemann costituisce uno dei 23 problemi elencati da David Hilbert all’inizio del ‘900. Non è ancora stata

dimostrata, anche se si è verificato che è vera per milioni di valori diversi di x. Di questa congettura e del suo stretto

legame con la distribuzione dei numeri primi tratta diffusamente L’enigma dei numeri primi di De Sautoy (opera

indicata nella bibliografia). 4

www.matematicamente.it Funzioni sui numeri interi di Stefano Borgogni

I primi numeri abbondanti sono: 12, 18, 20, 24, 30, 36; per trovare il primo abbondante dispari

3

occorre salire fino a 945 (numero che equivale a 35×27, cioè a 3 x5x7).

Tutti i multipli interi dei numeri abbondanti e dei numeri perfetti sono a loro volta numeri

abbondanti.

Numeri perfetti

Dei numeri perfetti si è già parlato diffusamente nel paragrafo 1.2; aggiungiamo soltanto che essi

costituiscono, evidentemente, lo “spartiacque” tra numeri difettivi e numeri abbondanti.

Numeri altamente composti

I numeri altamente composti sono numeri che hanno più divisori di qualsiasi intero positivo minore.

1a 2b nz

Riprendendo quanto detto nel paragrafo 1.1 a proposito della fattorizzazione, se n = p p … p ,

allora la somma dei divisori di n sarà (a+1) (b+1) … (z+1).

A partire da questa formula si possono stabilire due regole molto precise; affinché n sia un numero

altamente composto è necessario che:

i k numeri primi p siano esattamente i primi k numeri primi (2, 3, 5...), altrimenti potremmo

i

sostituirne uno con un primo minore, ottenendo così un numero minore di n con lo stesso

numero di divisori (ad esempio, 10=2×5, ma cambiando il 5 con il 3 si ha 6=2×3; 6 e 10 hanno

lo stesso numero di divisori per cui 10 non può essere altamente composto);

≥ ≥

b c etc., altrimenti,

la sequenza degli esponenti non deve essere crescente, cioè a

scambiandone due non in ordine si ha un numero minore di n con lo stesso numero di divisori

1 2 2 1

×3 può essere trasformato in 12 = 2 ×3 : dunque, 18 non è di sicuro un

(ad esempio, 18 = 2

numero altamente composto).

I primi 10 numeri altamente composti sono: 1, 2, 4, 6, 12, 24, 36, 48, 60 e 120.

Ovviamente, i numeri possono appartenere anche a più di una tipologia ma, a partire dalle stesse

definizioni, è facile ricavare che:

- Tutti i numeri primi sono anche difettivi (ma non viceversa).

- Non esistono numeri contemporaneamente difettivi e altamente composti; fanno eccezione i

primi due numeri pari, 2 e 4.

- L’unico numero che appartiene a tre categorie è 2 (primi, difettivi, altamente composti).

- Tutti i numeri altamente composti sono anche abbondanti (ma non viceversa).

5

www.matematicamente.it Funzioni sui numeri interi di Stefano Borgogni

FUNZIONI SUI NUMERI INTERI (Numeri da 1 a 200)

n Elenco dei divisori τ (n) σ(n) s(n) φ(n) π(n) Tipologie cui appartiene n

1 1 1 1 0 1 0 difettivi, alt.composti

2 1, 2 2 3 1 1 1 primi, difettivi, alt.composti

3 1, 3 2 4 1 2 2 primi, difettivi

4 1, 2, 4 3 7 3 2 2 difettivi, alt.composti

5 1, 5 2 6 1 4 3 primi, difettivi

6 1, 2, 3, 6 4 12 6 2 3 perfetti, alt.composti

7 1, 7 2 8 1 6 4 primi, difettivi

8 1, 2, 4, 8 4 15 7 4 4 difettivi

9 1, 3, 9 3 13 4 6 4 difettivi

10 1, 2, 5, 10 4 18 8 4 4 difettivi

11 1, 11 2 12 1 10 5 primi, difettivi

12 1, 2, 3, 4, 6, 12 6 28 16 4 5 abbondanti, alt.composti

13 1, 13 2 14 1 12 6 primi, difettivi

14 1, 2, 7, 14 4 24 10 6 6 difettivi

15 1, 3, 5, 15 4 24 9 8 6 difettivi

16 1, 2, 4, 8, 16 5 31 15 8 6 difettivi

17 1, 17 2 18 1 16 7 primi, difettivi

18 1, 2, 3, 6, 9, 18 6 39 21 6 7 abbondanti

19 1, 19 2 20 1 18 8 primi, difettivi

20 1, 2, 4, 5, 10, 20 6 42 22 8 8 abbondanti

21 1, 3, 7, 21 4 32 11 12 8 difettivi

22 1, 2, 11, 22 4 36 14 10 8 difettivi

23 1, 23 2 24 1 22 9 primi, difettivi

24 1, 2, 3, 4, 6, 8, 12, 24 8 60 36 8 9 abbondanti, alt.composti

25 1, 5, 25 3 31 6 20 9 difettivi

26 1, 2, 13, 26 4 42 16 12 9 difettivi

27 1, 3, 9, 27 4 40 13 18 9 difettivi

28 1, 2, 4, 7, 14, 28 6 56 28 12 9 perfetti

29 1, 29 2 30 1 28 10 prim