I numeri naturali

fondamentale concetto non è per niente semplice. Segnaliamo solo che un sistema per costruire operati-vamente i numeri naturali potrebbe essere quello di considerare la cardinalità dei seguenti insiemi (vedi la discussione nella pagina28del Capitolo1): ;,{ ; },{ ;,{ ; } },...

Per i nostri scopi, comunque, quello che interessa sono alcune delle proprietà dei numeri naturali e precisamente:

— il fatto che, come insieme, i naturali hanno una certa cardinalità;

— il fatto che l’insieme dei numeri naturali è un insieme ordinato con certe caratteristiche;

— il fatto che sull’insieme dei naturali si possano eseguire le operazioni di somma e prodotto le quali godono di certe proprietà;

— come conseguenza delle proprietà delle operazioni, la possibilità di risolvere certe equazioni e l’impossibilità di risolverne altre.

2.1.1. La cardinalità dei naturali

L’insieme dei numeri naturali, che indichiamo con N, è un insieme infinito ed è anzi il “più piccolo”

degli insiemi infiniti: ogni altro insieme infinito o è equipotente all’insieme dei naturali, o ha un sottoinsieme equipotente all’insieme dei naturali. La cardinalità dell’insieme dei naturali si indica con il simbolo ℵ₀. Dunque ogni insieme transfinito ha cardinalità maggiore o uguale ad ℵ₀. Un insieme che abbia cardinalità ℵ0si dice anchenumerabile e il motivo di questo nome è palese.

2.1.2. L’ordine nei naturali

Nell’insieme N è definito un ordine totale, detto ordine naturale che, nella forma antiriflessiva denotata con “<” (più comoda sui naturali che non quello nella forma riflessiva), gode dunque delle seguenti proprietà:

1. proprietà antiriflessiva: ∀n ∈ N, n ≮ n;

2. proprietà antisimmetrica: ∀m, n ∈ N, (m < n ⇒ n ≮ m);

3. proprietà transitiva: se m, n, p ∈ N, (m < n) ∧ (n < p) ⇒ (m < p);

4. proprietà di tricotomia: dati due naturali m ed n si ha m < n, oppure m = n, oppure n < m.

L’ordine gode inoltre delle seguenti ulteriori proprietà:

5. ogni numero naturalen ha un immediato seguente, n + 1;

6. ogni numero naturalen > 0 ha un immediato precedente, n − 1;

7. ogni sottoinsieme non vuoto di N ha un minimo, in particolare N ha 0 come minimo;

8. ogni insieme non vuoto e superiormente limitato di N ha un massimo.

Sussiste poi ilPrincipio di induzione di cui però in questo testo non ci occuperemo.

2.1.3. Le operazioni nei naturali

Cominciamo con il richiamare la nozione dioperazione (interna) su un insieme.

Definizione 2.1 (Operazione interna). Dato un insieme A, si chiama operazione (interna) in A ogni funzione ϕ: A× A → A. Le funzioni di questo tipo si sogliono, abitualmente, indicare con simboli come ◦, +, ×, /, ecc.

Matematica di base - 1 2.1. I numeri naturali Ricordiamo anche che, invece di scriverez = ϕ(x, y) per indicare l’immagine della coppia (x, y) tramite la funzione (operazione) ϕ, si scrive z = x + y, z = x × y, ecc., ovvero il simbolo che rappresenta la funzione si interpone tra i due elementi della coppia su cui agisce. In molti casi non si utilizza alcun simbolo, come per esempio nella moltiplicazione dove i due elementi della coppia vengono semplicemente scritti uno di fianco all’altro: z = xy. Ci sono anche altri modi di indicare le operazioni, ormai entrati nell’uso comune. Un esempio importante è quello dell’elevazione a potenza, dove il simbolo usuale, a tutti noto, èx^y.

Nell’insieme dei naturali sono anzitutto definite le operazioni diaddizione e moltiplicazione: nell’addi-zione il risultato dell’operanell’addi-zione si chiamasomma dei due numeri, che prendono il nome di addendi; se gli addendi sonoa e b, la somma di indica con a + b. Nella moltiplicazione il risultato della operazione si chiamaprodotto dei due numeri, che prendono il nome di fattori; se i fattori sono a e b, il prodotto si indica cona × b, oppure con a · b, oppure più semplicemente con ab⁽¹⁾. Queste operazioni godono delle seguenti importanti proprietà.

1. Proprietàassociativa:

∀a, b, c ∈ N, (a + b) + c = a + (b + c); (ab)c = a(b c);

questa proprietà consente di evitare l’uso delle parentesi nelle addizioni o moltiplicazioni ripetute:

hanno dunque senso le scritturea + b + c e ab c.

2. Proprietàcommutativa:

∀a, b ∈ N, a + b = b + a; ab = ba.

3. Esistenza dell’elemento neutro⁽²⁾:

∀a ∈ N, a + 0 = a; a1 = a.

4. Proprietàdistributiva della moltiplicazione rispetto all’addizione:

∀a, b, c ∈ N, a(b + c) = ab + ac.

5. Legge dell’annullamento del prodotto:

ab = 0 ⇔ (a = 0) ∨ (b = 0).

6. Legge dicancellazione della somma:

a + c = b + c ⇔ a = b.

1Le operazioni che stiamo trattando si chiamanoaddizione e moltiplicazione, mentre somma e prodotto si riferiscono al risultato delle operazioni. Tuttavia spesso si usano i termini somma e prodotto anche per indicare le operazioni, anche se si tratta di un abuso di linguaggio. Anche noi ogni tanto faremo così.

2Non tutti concordano nel ritenere che l’insieme dei naturali comprenda lo zero. Il discorso che abbiamo fatto a proposito di una possibile costruzione dei naturali come cardinalità di certi insiemi, rende opportuna invece l’inclusione dello zero in N. Tuttavia esistono altre considerazioni che porterebbero alla sua esclusione, e dunque il fare una scelta o l’altra è sostanzialmente questione di gusto: per questo è molto importante controllare, nell’elenco delle notazioni, qual è la convenzione seguita nel testo che si sta consultando.

7. Legge dicancellazione del prodotto:

(c 6= 0) ⇒ (ac = b c ⇔ a = b ).

8. Compatibilità dell’ordine con l’addizione:

a < b ⇔ a + c < b + c 9. Compatibilità dell’ordine con la moltiplicazione:

(c > 0) ⇒ (a < b ⇔ ac < b c).

L’introduzione delle due operazioni di addizione e sottrazione rende l’insieme dei numeri naturali una struttura algebrica, molto semplice: si tratta precisamente di un monoide o semigruppo abeliano dotato di unità rispetto ad entrambe le operazioni. La necessità di avere a disposizione strutture algebriche sempre più ricche è uno dei motivi che portano ad ampliare l’insieme dei numeri in uso nella matematica.

2.1.4. Le prime equazioni nei naturali

L’introduzione delle operazioni di addizione e moltiplicazione ci conduce immediatamente a conside-rare problemi come i due seguenti:

1. dati due numeri naturalia e b determinare, se esiste, un numero naturale x tale che x + b = a;

2. dati due numeri naturalia e b determinare, se esiste, un numero naturale x tale che x · b = a.

Si tratta dei primi esempi diequazioni in una incognita: esse conducono, rispettivamente, all’introdu-zione delle operazioni disottrazione e di divisione, anche se il termine “operazione” è inappropriato, secondo la definizione2.1che abbiamo dato; infatti né la sottrazione, né la divisione sono definite in tutto N × N. Si danno precisamente le due seguenti definizioni.

Definizione 2.2 (Sottrazione). Dati i numeri naturali a e b, con a ≥ b, si chiama differenza di a e b (nell’ordine!) l’unico numero x che risolve l’equazione x + b = a. Tale numero x si indica con a − b. Il numero a si chiama minuendo, il numero b si chiama sottraendo.

Definizione 2.3 (Divisione). Dati i numeri naturali a e b, con b 6= 0, si chiama quoziente di a e b (nell’ordine!) l’unico numero x, se esiste, che risolve l’equazione x · b = a. Tale numero x si indica con a/b o con a : b. Il numero a si chiama dividendo, il numero b si chiama divisore.

Si tengano ben presenti le seguenti importanti osservazioni.

1. La sottrazione è possibile solo se il minuendo è maggiore o uguale al sottraendo.

2. La divisione non è mai possibile se il divisore è zero,nemmeno se il dividendo è zero: non ha alcun senso la scritturaa/0, e men che mai la scrittura 0/0⁽³⁾.

3Spesso, soprattutto sui testi elementari, si trova scritto che 0/0 è indeterminato. Una tale affermazione potrebbe anche avere un senso in quanto l’equazionex · 0 = 0 è verificata qualunque sia il numero x. È però preferibile limitarsi a fornire la soluzione (se c’è!) dell’equazionex · b solo ed esclusivamente quando b 6= 0, e questo per una serie di motivi che qui non possiamo riportare.

Matematica di base - 1 2.1. I numeri naturali 3. La divisione (con divisore diverso da zero) non è sempre possibile: quando lo è, si dice chea è multiplo di b, o anche che o anche che b è un divisore di a, o ancora che b divide a e si scrive b | a.

4. La sottrazione e la divisionenon godono della proprietà associativa:

(a − b ) − c 6= (a − (b − c); (a/b )/c 6= a/(b /c).

5. La sottrazione e la divisionenon godono della proprietà commutativa:

a − b 6= b − a; a/b 6= b/a.

Si noti che la mancanza della proprietà commutativa è evidenziata anche dalla nomenclatura utilizzata: mentre nella addizione e moltiplicazione i due “operandi” hanno lo stesso nome (addendi o fattori), nella sottrazione e divisione no, e questo proprio per il fatto che non vale la proprietà commutativa.

L’impossibilità di risolvere in ogni caso le equazioni qui considerate è una delle ragioni che spingono ad ampliare l’insieme di numeri che si usano in matematica.

2.1.5. L’elevazione a potenza

In N si definisce anche l’operazione di elevamento a potenza, parzialmente come semplice abbreviazione della scrittura di certi prodotti. Precisamente si dà la definizione che segue.

Definizione 2.4(Potenza). Dati a e n ∈ N, con n > 0 si pone (2.1) a¹= a; aⁿ= a · a · · · a

| {z }

n fattori

, se n > 1.

Si pone inoltre

(2.2) a⁰= 1, ∀a > 0; 0ⁿ= 0, ∀n > 0.

Nella scrittura aⁿ, il numero a si chiama base, il numero n si chiama esponente.

Le formule (2.1) e (2.2) potrebbero anche essere riscritte, in maniera ricorsiva, come segue:

(2.3) Sea > 0, a⁰= 1, aⁿ⁺¹= a · aⁿ; sen > 0, 0ⁿ= 0 .

Si noti che al simbolo 0⁰ non è attribuito alcun significato. Si noti altresì che la potenza è solo parzialmente un “modo compatto” per scrivere un prodotto con fattori tutti uguali: i simbolia¹ed a⁰non sono in alcun modo legati all’operazione di moltiplicazione. Torneremo nel capitolo7, in cui richiameremo le proprietà delle potenze, sui motivi che giustificano queste definizioni.

Sussistono le seguenti proprietà formali delle potenze. Sea, b, m, n sono naturali maggiori di 0 si ha (2.4) aⁿa^m= a^n+m; (aⁿ)^m= a^nm; aⁿbⁿ= (ab )ⁿ; sen ≥ m, aⁿ

a^m = a^n−m.

Quando hanno senso, alcune delle (2.4) si estendono anche ai casi in cui qualcuno dei numeri che vi compaiono sono zero.

2.1.6. La precedenza nelle operazioni successive

Nel caso di più operazioni da eseguirsi su numeri, la regola base è che esse si eseguono nell’ordine in cui si presentano, a meno che non intervengano delle parentesi ad alterare questo “ordine naturale”.

Per esempio la scrittura 24 : 6 : 2 dà come risultato 2, in quanto si esegue prima 24 : 6 = 4 e successivamente 4 : 2 = 2. Si otterrebbe lo stesso risultato scrivendo (24 : 6) : 2. La scrittura 24 : (6 : 2) dà invece come risultato 8, in quanto la presenza delle parentesi impone di eseguire per primo la divisione 6 : 2 = 3 e successivamente la 24 : 3 = 8.

Per evitare di usare troppe parentesi si è comunque convenuto di assegnare ad alcune operazioni una precedenza sulle altre. Per quanto riguarda le operazioni fin qui definite si ha precisamente:

1. l’elevazione a potenza deve essere eseguita per prima;

2. successivamente devono essere eseguite le moltiplicazioni e divisioni nell’ordine in cui si presenta-no;

3. infine devono essere eseguite le addizioni e sottrazioni.

Per esempio la scrittura 3 + 5 × 2³dà come risultato 43 in quanto si esegue dapprima 2³= 8, poi 5 × 8 = 40 e successivamente 3 + 40 = 43.

Al di fuori di queste regole le operazioni si eseguono nell’ordine in cui si presentano. Per esempio 12 : 6 × 2 dà come risultato 4, in quanto non esiste precedenza tra divisione e moltiplicazione.

C’è comunque una situazione che è opportuno segnalare perché fonte di ambiguità, e riguarda l’elevazione a potenza con scritture (molto comuni in tutti i testi!) del tipo

a^bc.

Per capire meglio, ragioniamo su un esempio concreto. Le due scritture seguenti (2³)² e 2⁽³²⁾

non pongono alcun problema interpretativo e forniscono come risultato, rispettivamente, 64 e 512. Ma la scrittura

2³²

come va interpretata? Purtropponon c’è una convenzione univoca su questo: per alcuni significa (2³)²= 64, per altri 2⁽³²⁾= 512, e questo anche sui software di calcolo simbolico e sulle calcolatrici tascabili. Basta provare a scrivere 2ˆ3ˆ2 su una calcolatrice tascabile (e di solito si ottiene 64) o su un software come Mathematica, Maple, Geogebra (dove si ottiene 512).

Noi adotteremo la convenzione più diffusa e cioè

(2.5) a^bc = a^(bc),

che equivale a dire cheaˆbˆc = aˆ(bˆc), ovvero che l’elevazione a potenza è, come si usa dire, associativa a destra. Questa nomenclatura serve a richiamare la differenza con, per esempio, la divisione, per la quale, come già osservato, si ha

a/b/c = (a/b)/c ,

situazione che si esprime a parole dicendo che la divisione èassociativa a sinistra.

Matematica di base - 1 2.1. I numeri naturali

2.1.7. Divisibilità. Numeri primi

Nell’insieme dei numeri naturali è definita un’operazione didivisione con resto. Segnaliamo che, come già per la sottrazione e divisione, non si tratta di una operazione nel vero senso della parola, in quanto non è un’applicazione di N × N in N. Essa si basa sul seguente teorema.

Teorema 2.5. Dati due numeri naturali a e b, con b > 0, esiste una e una sola coppia (q, r) di numeri naturali tali che

1. a = qb + r, 2. (0 ≤) r < b.

I numeri q ed r prendono rispettivamente il nome di quoziente e resto della divisione di a per b.

Osserviamo che se èr = 0, significa che la divisione tra a e b è possibile, nel senso della definizione 2.3, e si usano i termini di multiplo, divisibile e divisore, già allora introdotti.

Sea è divisibile per b si dice anche che b divide a e si usa la seguente scrittura

(2.6) b | a .

La determinazione diq ed r si fa con il classico algoritmo della divisione, noto a tutti fin dai tempi della scuola primaria.

Definizione 2.6(Numero primo). Un numero naturale p si dice primo se è maggiore di 1 ed è divisibile solo per se stesso e per 1.

È immediato constatare che 2 è il più piccolo primo ed è anche l’unico primo pari. I successivi primi sono 3, 5, 7, .... I numeri primi giocano un’importanza cruciale in moltissime applicazioni: segnaliamo solo, a titolo d’esempio, il loro uso nella moderna crittografia.

I numeri primi possono essere considerati i “mattoni” con cui sono costruiti tutti i numeri naturali, nel senso precisato dal seguente teorema.

Teorema 2.7(Teorema fondamentale dell’aritmetica). Ogni numero naturale maggiore di 1 o è primo o è esprimibile come prodotto di fattori primi e tale espressione è unica a meno dell’ordine in cui i fattori sono scritti.

Questo teorema si può compendiare nella formula seguente (2.7) ∀n ∈ N, n > 1, n = p₁ⁱ¹p₂ⁱ²··· p_k^ik,

dove abbiamo raggruppato, usando l’operazione di potenza, tutti i fattori primi tra di loro uguali. Si può naturalmente supporre che i fattori che compaiono nella formula (2.7) siano scritti in ordine crescente.

Si ha, per esempio, 28693665 = 3²· 5 · 7³· 11 · 13².

Il contenuto di questo teorema è tutt’altro che banale (e la dimostrazione dell’unicità della decomposi-zione è abbastanza difficile). La verifica concreta della decomponibilità di un numero in un prodotto di primi può richiedere anni di lavoro anche su potenti computer. A questo proposito è rimasto famoso un articolo di Martin Gardner pubblicato suScientific American nell’agosto del 1977. In relazione a un

problema di crittografia, il problema proposto nell’articolo era quello di scomporre in fattori primi un numero di 129 cifre, e precisamente

n = 1143816257578888676692357799761466120102182967212423625625618

42935706935245733897830597123563958705058989075147599290026879543541.

Nell’aprile del 1994, solo⁽⁴⁾17 anni dopo, quella scomposizione fu scoperta: i due numeri p e q, tali che n = pq sono

p = 3490529510847650949147849619903898133417764638493387843990820577, q = 32769132993266709549961988190834461413177642967992942539798288533,

il primo di 64 e il secondo di 65 cifre. Oggi si ritiene che un numero di 500 cifre possa richiedere oltre un secolo di calcoli per decidere se è primo o no.

I numeri primi diventano sempre più radi man mano che si considerano naturali sempre più grandi.

Per esempio ci sono

— 168 primi tra 1 e 1000;

— 135 primi tra 1001 e 2000;

— 127 primi tra 2001 e 3000;

— 120 primi tra 3001 e 4000;

— 119 primi tra 4001 e 5000.

Tuttavia i primi sono infiniti, come prova un celeberrimo teorema dovuto ad Euclide, di cui riportiamo la dimostrazione perché è considerata una delle più eleganti dimostrazioni in matematica.

Teorema 2.8(Infinità dei primi). Esistono infiniti numeri primi.

Dimostrazione. Supponiamo che esista solo un sistema finito di primi: p₁, p₂, p₃, ..., p_k, e consideriamo il naturale

n = p₁p₂p₃··· p_k+ 1 .

Questo numero non è divisibile per nessuno dei primip₁, p₂, p₃, ..., p_k, in quanto il resto della divisione din per uno di questi primi dà 1. Dunque o è primo (e dunque è assurdo che i primi siano solo quelli elencati), o deve essere divisibile per qualche primo diverso da quelli elencati, per il teorema fondamentale dell’aritmetica, e quindi è ancora assurdo supporre che i primi siano solo quelli elencati.

Si noti che questa dimostrazione non produce un metodo per costruire nuovi numeri primi a partire da un dato insieme di primi. Per esempio, dati i primi 2, 3, 5, 7, 11, 13 il numero che si costruisce a partire da essi con l’algoritmo di Euclide, e cioè

2 × 3 × 5 × 7 × 11 × 13 + 1 = 30031,

non è primo, ma è il prodotto dei primi 59 e 509 che non stanno nella lista precedente. La ricerca di formule per la generazione di numeri primi ha occupato l’attenzione di molti matematici, specie nel

4In realtà quando l’articolo fu pubblicato si riteneva necessario un tempo molto più lungo per questo scopo. L’avvento di internet e la collaborazione di 600 volontari di una ventina di paesi sotto la guida di un gruppo di ricercatori permisero invece la risoluzione dell’enigma in un tempo relativamente breve (circa otto mesi di lavoro).

Matematica di base - 1 2.1. I numeri naturali diciassettesimo secolo. Un famoso esempio, dovuto ad Eulero, è quello della formulax²+ x + 41 che produce numeri primi per tutti i naturalix ≤ 39, mentre non produce un primo per x = 40. Non possiamo però dilungarci oltre su questo argomento.

Definizione 2.9 (Numeri primi tra di loro). Due naturali non nulli si dicono primi tra di loro o mutuamente primise 1 è l’unico loro divisore comune.

Il numero 1 è naturalmente primo con ogni altro numero naturale. È ovvio che due naturalia e b sono primi tra di loro se e solo se non esiste alcun fattore primo comune tra la scomposizione dia e di b.

Se due numeria e b non sono primi tra di loro ha grande interesse la determinazione del loro massimo comun divisore, cioè del massimo (certamente esistente perché non maggiore né di a né di b) dei loro divisori comuni, a volte indicato con MCD(a, b). Se essi sono primi tra di loro, questo massimo comun divisore è chiaramente 1. L’algoritmo più elementare per trovare il massimo comun divisore è quello di scomporre i due numeri in fattori primi e poi di fare il prodotto dei fattori comuni con il minimo esponente. Tuttavia esiste un algoritmo molto efficiente, dovuto ad Euclide, per la determinazione del massimo comun divisore, algoritmo presentato nel teorema che segue.

Teorema 2.10(Algoritmo euclideo delle divisioni successive). Sia a e b (in cui possiamo supporre, senza perdere di generalità, a > b) e si eseguano le seguenti successive divisioni con resto

a = d₁b + r₁ con 0 ≤ r₁< b b = d₂r₁+ r₂ con 0 ≤ r₂< r₁ r₁= d₃r₂+ r₃ con 0 ≤ r3< r₂

... ...

fin quando si ottiene resto zero (dopo meno di b passi). Il massimo comun divisore tra a e b è l’ultimo resto non nullo.

Esempio 2.1. Siano dati i numeri 326059 e 164143. Procedendo come indicato nel teorema2.10si ottiene:

326059 = 1 × 164143 + 161916, 164143 = 1 × 161916 + 2227, 161916 = 72 × 2227 + 1572,

2227 = 1 × 1572 + 655, 1572 = 2 × 655 + 262,

655 = 2 × 262 + 131, 262 = 2 × 131 + 0,

da cui si deduce che il massimo comun divisore tra i numeri dati è 131.

Due numeri naturalia e b non nulli hanno sempre un multiplo comune, per esempio il loro prodotto.

Nelle applicazioni ha interesse il più piccolo di questi multipli comuni (certamente esistente per le specifiche proprietà dell’ordine nei naturali), detto ilminimo comune multiplo, a volte indicato con mcm(a, b). L’algoritmo più elementare per trovare il minimo comune multiplo è quello di scomporre i

due numeri in fattori primi e poi di fare il prodotto dei fattori comuni e non comuni con il massimo esponente. La ricerca si può fare però anche determinando il massimo comun divisore con l’algoritmo euclideo delle divisioni successive e osservando poi che, in base alla definizione, si ha facilmente che ab = MCD(a, b)mcm(a, b).

Esempio 2.2. Il minimo comune multiplo dei due numeri 326059 e 164143 già considerati nell’esempio precedente è dato da

mcm(326059,164143) =326059 × 164143

131 = 408551927.

2.1.8. Qualche criterio di divisibilità

Valgono i seguenti criteri di divisibilità⁽⁵⁾la maggior parte dei quali dimostrabili in maniera elementare.

1. Un numero è divisibile per 2 se e solo se è pari.

2. Un numero è divisibile per 3 se e solo se è divisibile per 3 la somma delle sue cifre.

3. Un numero è divisibile per 4 se e solo se è divisibile per 4 il numero formato dalle ultime due cifre.

4. Un numero è divisibile per 5 se e solo se termina per 5 o per 0.

5. Un numero è divisibile per 8 se e solo se è divisibile per 8 il numero formato dalle sue ultime tre cifre.

6. Un numero è divisibile per 9 se e solo se è divisibile per 9 la somma delle sue cifre.

7. Un numero è divisibile per 10 se e solo se termina per 0.

8. Un numero è divisibile per 11 se e solo se è divisibile per 11 il numero intero dato dalla somma delle cifre di posto pari meno quello dato dalla somma delle cifre di posto dispari. Di solito si parte dall’ultima cifra (cifra delle unità), che è di posto “0”, in quanto corrisponde alla potenza 0 di 10.

Esistono anche altri criteri di divisibilità (per esempio per 7) ma sono più complicati e di uso poco frequente.

Nel documento MATEMATICA DI BASE (pagine 65-74)