CAPITOLO  2

Aritmetica in Z

2.1  La divisione euclidea

DEFINIZIONE 1 Dati due interi a e b, con b ¹ 0, si dice che b divide a se esiste un intero q tale che a = bq. In questo caso si usa la notazione b|a e si dice anche che b é un divisore o fattore di a, ovvero che a é un multiplo di b, o ancora che a é divisibile per b. ¨

OSSERVAZIONE 2 Si noti che, per definizione, 0 non divide alcun intero. ¨

ESEMPIO 3 L'intero -3 divide 21, perché risulta 21 = (-3)(-7). Analogamente, abbiamo 25|0, perché 0 = 25·0. ¨

Valgono le seguenti proprietá:

· Ogni intero non nullo é divisibile per se stesso (proprietá riflessiva della divisibilitá).

· 1 e -1 sono gli unici divisori di 1,

· 0 é divisibile per ogni intero non nullo.

· a| b e b| c   Þ   a|c (proprietá transitiva della divisibilitá).

· a| b e b| a   Û   a = ±b (in questo caso a e b si dicono associati).

· Se c é un divisore di a e di b, allora c divide ogni intero del tipo ma+nb, ove m,n sono interi.

OSSERVAZIONE 4 E' chiaro che ogni intero non nullo a é multiplo di 1, -1, a, -a. Per tale motivo 1, -1, a, -a si dicono divisori banali di a. Nel caso a ¹ ±1 , un divisore di a diverso da a e -a si dice proprio. ¨

ESEMPIO 5 Gli interi 2,3,5,7,11 posseggono soltanto divisori banali. L'intero 15, oltre ai divisori banali, possiede quattro divisori non banali: 3, -3, 5 e -5. ¨

ESERCIZIO 6 Due interi distinti hanno gli stessi divisori se, e solo se, sono associati.

TEOREMA 7 (divisione euclidea) Siano a,b interi con b > 0. Allora esiste un'unica coppia di interi (q,r) per cui risulta

DIMOSTRAZIONE.   Cominciamo a provare la (2.1) nel caso a ³ 0, osservando che, se é a < b, risulta (q,r) = (0,a), cioé a = b·0+a. Possiamo, quindi, suppore a ³ b e procedere per induzione su a. In queste ipotesi, essendo a > a-b ³ 0, possiamo scrivere a-b = bq₁+r, con 0 £ r < b, da cui ricaviamo

Nel caso a < 0, risulta -a > 0 e, per quanto giá provato, esiste ed é unica la coppia (q₀,r₀) tale che

Proviamo, ora, l'unicitá della coppia (q,r). A tale scopo, nell'ipotesi che valga la (2.1), sia (q¢,r¢) una coppia di interi per cui a = bq¢+r¢ e 0 £ r¢ < b e supponiamo q¢ < q. Allora é q-q¢ ³ 1 e abbiamo

ESEMPIO 9 Per a = -15 e b = 2, risulta q = -8 e r = 1. ¨

OSSERVAZIONE 10 Notiamo che, nel corso della dimostrazione della proposizione precedente, il procedimento usato per trovare il quoziente e il resto della divisione tra a( > 0) e b( > 0) non é altro che l'usuale algoritmo della divisione mediante sottrazioni successive, noto al Lettore dalle scuole medie: si sottrae ripetutamente b ad a fino ad ottenere un intero r non negativo e minore di b (il numero di sottrazioni é il quoziente q ed r il resto). ¨

DEFINIZIONE 11 La funzione |    |  :  a Î Z®|a| Î N_o definita da

Il teorema che segue é una semplice generalizzazione del precedente.

TEOREMA 12 (divisione euclidea in Z) Siano a,b interi con b ¹ 0. Allora esiste un'unica coppia di interi (q,r) per cui risulta a = bq+r e 0 £ r < |b|.

COROLLARIO 13 Siano a,b due interi con b ¹ 0. Allora b divide a se, e solo se, é zero il resto della divisione di a per b.

2.2  Sistemi di numerazione

Sia a ³ 2 un fissato intero e consideriamo un arbitrario intero n > 0. Applicando ripetutamente la divisione euclidea, possiamo scrivere in un unico modo:

OSSERVAZIONE 1 Eliminando i quozienti q_j dalle precedenti relazioni (2.3), otteniamo

DEFINIZIONE 2 Sia

OSSERVAZIONE 3 La definizione precedente, naturalmente, presuppone che si sia fissato un insieme di a simboli, detti cifre, per rappresentare tutti gli interi maggiori o uguali a zero e minori di a. A volte, specialmente in teoria dell'informazione, per le cifre si usa il termine inglese digit. Nel caso a = 2 le cifre vengono chiamate anche bit. ¨

DEFINIZIONE 4 La funzione che ad ogni intero positivo associa la successione delle cifre che lo rappresentano in base a si chiama sistema di numerazione in base a. ¨

· Il sistema in base dieci o decimale, le cui cifre sono nell'ordine: 0,1,2,3,4,5,6,7,8,9.

· Il sistema in base due o binario, le cui cifre sono nell'ordine: 0,1.

· Il sistema in base otto le cui cifre sono nell'ordine: 0,1,2,3,4,5,6,7.

· Il sistema in base sedici o esagesimale, le cui cifre da zero a nove sono quelle decimali e le rimanenti sono: A:=dieci, B:=undici, C:=dodici, D:=tredici, E:=quattordici, F:=quindici.

I sistemi di numerazione che abbiamo introdotto si chiamano posizionali: il valore da attribuire ad una cifra che compare nella rappresentazione di un numero non dipende solo dalla cifra ma anche dalla sua posizione. Le origini del sistema di numerazione decimale non sono del tutto chiare; é molto probabile che fu ideato dagli indiani, forse nel VI secolo D.C., e successivamente trasmesso agli arabi. Tra coloro che maggiormente contribuirono a diffondere in Europa questo sistema di numerazione attorno al XIII secolo vi fu Leonardo Pisano Fibonacci (1170-1250), che con il suo "Liber Abaci" (1228) presentó il sistema posizionale e le conseguenti regole di calcolo, evidenziando i notevoli vantaggi del nuovo metodo.Il piú antico testo europeo contenente le cifre decimali, tranne lo zero, risale al 976 D.C. e si trova nel "Codex Vigilanus" (vedi Figura. 2.2). ¨

ESEMPIO 6 (109)_dieci = (1101101)_due = (6D)_sedici. ¨

ESEMPIO 7 a = (10)_a , per ogni intero a > 1. ¨

2.3  Massimo comune divisore e algoritmo di Euclide

Assegnati due interi a e b, un loro divisore comune é un intero c che divide sia a che b.

ESEMPIO 1 I divisori comuni di 12 e 18 sono: ±1, ±2, ±3, ±6. ¨

DEFINIZIONE 2 Un intero d si dice massimo comune divisore di due assegnati interi a e b se d é un divisore comune di a e b e se ogni divisore comune di a e b é anche un divisore di d. ¨

OSSERVAZIONE 3 Se a e b hanno un massimo comune divisore d, allora ne hanno esattamente due: d e -d. ¨

ESEMPIO 4 I massimi comuni divisori di 12 e 18 sono 6 e -6. ¨

OSSERVAZIONE 5 Un massimo comune divisore di a e b é anche un massimo comune divisore di a e -b. ¨

OSSERVAZIONE 6 Sia a = bq+r. Allora un intero d é massimo comune divisore di a e b se, e solo se, d é massimo comune divisore di b ed r. ¨

TEOREMA 7 (algoritmo di Euclide) Se a,b sono interi non nulli, allora esiste un massimo comune divisore di a e b.

DIMOSTRAZIONE.   In forza dell'osservazione  5  non é restrittivo supporre che a e b siano positivi. Costruiamo la seguente successione di divisioni, fino ad ottenere un resto uguale a zero: 

OSSERVAZIONE 8 Si noti che il procedimento riportato nella (2.5) é un vero e proprio algoritmo (detto anche delle divisioni successive) per il calcolo di un massimo comune divisore di a e b: il massimo comune divisore cercato é l'ultimo resto non nullo nella successione di divisioni (2.5). Tale algoritmo é stato descritto per la prima volta duemilatrecento anni fa da Euclide nei suoi "Elementi" e, ancora oggi, é il piú efficiente che si conosca. ¨

ESEMPIO 9 Vediamo come lavora l'algoritmo (2.5) nel caso a = 306 e b = 135:

TEOREMA 10 (identitá di Bézout) Siano a,b interi non nulli e d un loro massimo comune divisore. Allora d si puó scrivere come combinazione lineare di a e b a coefficienti in Z, esistono cioé due interi m,n tali che

DIMOSTRAZIONE.   Partendo dalla prima delle uguaglianze (2.5) e andando verso le successive, abbiamo

ESEMPIO 11 Applichiamo il procedimento del teorema precedente all'esempio  9 , ove a = 306, b = 135 e d = 9. Abbiamo:

ESERCIZIO 12 Provare che due interi non nulli a,b hanno un unico massimo comune divisore positivo (che si denota con MCD(a,b) o con (a,b)).

ESERCIZIO 13 Sia d = ±MCD(a,b) e supponiamo a = da₁ e b = db₁. Provare che risulta MCD(a₁,b₁) = 1 (in questo caso a₁ e b₁ si dicono primi tra loro o coprimi).

ESERCIZIO 14 Provare che due interi a,b sono coprimi se, e solo se, esistono m,n Î Z tali che ma+nb = 1.

ESERCIZIO 15 Siano a e b coprimi e a divida bc. Provare che a divide c.

PROPOSIZIONE 16 Provare che, se a,b,c sono interi con a,b ¹ 0, l'equazione

DIMOSTRAZIONE.   Se ([`x],[`y]) é una soluzione intera della (2.7), d divide a[`x]+b[`y] = c, perché d divide sia a che b. Viceversa, se é c = kd, con k Î Z, e d = ma+nb (cfr.(2.6)), risulta

PROPOSIZIONE 17 Nell'ipotesi che l'equazione (2.7) abbia una soluzione intera (h,k), sia d un massimo comune divisore di a e b e sia a = da₁, b = db₁. Allora le soluzioni intere della (2.7) sono tutte e sole quelle del tipo

DIMOSTRAZIONE.   É immediato verificare che una coppia del tipo (2.8) é una soluzione intera della (2.7). Supponiamo, dunque, che ([`x],[`y]) sia una soluzione intera della (2.7) e osserviamo che, in queste ipotesi, si ha:

DEFINIZIONE 18 Un intero m si dice minimo comune multiplo di due assegnati interi non nulli a e b se a e b dividono m e se ogni multiplo di a e b é anche un multiplo di m. ¨

ESERCIZIO 19 Sia d = MCD(a,b) e ab = dm. Provare che m é un minimo comune multiplo di a,b.

ESERCIZIO 20 Se a e b sono coprimi, provare che ab é un minimo comune multiplo di a e b.

ESERCIZIO 21 Provare che due interi non nulli a,b hanno esattamente due minimi comuni multipli, che sono l'uno l'opposto dell'altro (l'unico minimo comune multiplo positivo di a,b si denota con mcm(a,b)).

ESERCIZIO 22 Estendere le definizioni di minimo comune multiplo e di massimo comune divisore al caso di piú di due interi.

2.4  Il teorema fondamentale dell'aritmetica

In questo paragrafo faremo vedere che ogni intero diverso da zero si puó scrivere, in modo essenzialmente unico, come prodotto di numeri speciali, i numeri primi, che fra poco definiremo.

DEFINIZIONE 1 Un elemento u Î Z si dice invertibile se esiste un intero u¢ tale che uu¢ = 1. ¨

ESERCIZIO 2 Provare che gli unici elementi invertibili di Z sono 1 e -1.

DEFINIZIONE 3 Un elemento a Î Z si dice irriducibile se é diverso da 0,1,-1 e i suoi unici divisori sono quelli banali, cioé 1,-1,a,-a. ¨

ESERCIZIO 4 Provare che un intero a, diverso da 0,1,-1, é irriducibile se, ogni qualvolta a si scrive come prodotto a = bc con b,c Î Z, allora uno tra b e c é invertibile; cioé b = ±1 e c = ±a, oppure b = ±a e c = ±1.

DEFINIZIONE 5 Un elemento p Î Z si dice primo se é diverso da 0,1,-1 e se ogni qualvolta divide un prodotto ab, con a,b Î Z, allora divide uno almeno dei fattori. ¨

ESERCIZIO 6 Provare che un intero a é irriducibile (risp. primo) se, e solo se, -a é irriducibile (risp. primo).

PROPOSIZIONE 7 Un numero intero é primo se, e soltanto se, é irriducibile.

DIMOSTRAZIONE.   Sia p un primo e supponiamo p = ab. Poiché p|ab, abbiamo che p|a o p|b, cioé a = ph o b = pk, con h,k Î Z. Ne segue che p = phb o p = pak, cioé hb = 1 o ak = 1 e quindi uno tra a e b é invertibile. Abbiamo cosí che p é irriducibile.
Sia ora p un irriducibile e supponiamo p|ab. Posto ph = ab, supponiamo per esempio che p non divida a. In queste ipotesi é MCD(a,p) = 1 ed esistono due interi m,n tali che ma+np = 1. Allora risulta mab+npb = b e, dividendo p il primo membro di questa uguaglianza, deve dividere b. Abbiamo cosí che p é primo. ¨

ESERCIZIO 8 Sia p un primo che divide il prodotto a₁a₂¼a_k. Allora p divide almeno uno dei fattori a₁,a₂,... ,a_k.

L'importanza dei numeri primi in aritmetica risiede nella validitá del seguente teorema.

TEOREMA 9 (teorema fondamentale dell'aritmetica) Ogni intero n ³ 2 puó essere fattorizzato nella forma n = p₁p₂¼p_k, ove p₁,p₂,... ,p_k sono primi positivi (non necessariamente distinti) e tale fattorizzazione é unica, a meno dell'ordine dei fattori.

DIMOSTRAZIONE.   Riportiamo una dimostrazione che fa uso del principio di buon ordinamento.

· Sia X l'insieme degli interi n ³ 2 che non ammettono una fattorizzazione in primi positivi. Se assumiamo X ¹ Æ, possiamo considerare il minimo m di X.

· L'intero m non é primo (altrimenti m Ï X) e quindi é m = ab, con 1 < a,b < m. Ne segue che a,b Ï X.

· Gli interi a,b, sono fattorizzabili in primi positivi e da ció segue che m é fattorizzabile in primi; un assurdo.

· Sia Y l'insieme degli interi n ³ 2 che ammettono fattorizzazioni distinte in primi, a meno dell'ordine dei fattori. Se Y ¹ Æ, possiamo considerare il minimo m di Y e due sue diverse fattorizzazioni del tipo desiderato m = p₁p₂¼p_k e m = p¢₁p¢₂¼p¢_l.

· p₁| m = p¢₁p¢₂¼p¢_l Þp₁ divide almeno uno dei p¢_j.

Non é restrittivo supporre che p₁| p¢₁ e da ció segue p₁ = p¢₁. Cosí abbiamo che l'intero [m/(p₁)] ³ 2 é minore di m e possiede due distinte fattorizzazioni del tipo desiderato

COROLLARIO 10 Ogni intero n ³ 2 puó essere scritto nella forma

COROLLARIO 11 Siano a,b > 1 due interi e

COROLLARIO 12 Sia m un intero tale che |m| ³ 2. Allora m possiede una fattorizzazione in primi. Inoltre, se

OSSERVAZIONE 13 E' da notare che se 1 e -1 fossero considerati primi, il teorema fondamentale dell'aritmetica sarebbe falso. ¨

OSSERVAZIONE 14 Il teorema fondamentale dell'aritmetica assicura che la conoscenza dell'insieme di tutti i numeri primi permette di costruire, mediante la moltiplicazione, tutti gli altri interi. E', inoltre, intuibile che le proprietá algebriche di un intero n dipendono dai primi che compaiono nella sua fattorizzazione in primi. Molti autori, usando un'allegoria estremamente calzante, paragonano ogni primo ad un tipo di mattone e gli interi alle case che possono costruirsi con questi mattoni. Purtroppo lo studio dei numeri primi, che é uno dei capitoli fondamentali della teoria dei numeri, presenta notevoli difficoltá e, ancora oggi, non si riesce a risolvere molti dei problemi ad essi relativi. E' questo uno dei motivi per cui l'aritmetica riveste un ruolo centrale nella crittografia moderna. L'efficienza di molti sistemi crittografici, infatti, dipende dalla possibilitá di trovare facilmente numeri primi "molto grandi" e dalla difficoltá di decomporre in fattori primi gli interi "molto grandi". ¨

2.5  Alcune proprietá dei primi

Il teorema che segue stabilisce la non finitezza dell'insieme dei numeri primi. La sua dimostrazione, nota come "argomento di Euclide" e riportata negli "Elementi," pur nella sua semplicitá, rimane per molti una delle piú belle ed eleganti di tutti i tempi.

TEOREMA 1 (teorema di Euclide) L'insieme P dei numeri primi é infinito.

DIMOSTRAZIONE.   Si supponga che P = {p₁,p₂,... ,p_t} sia finito e si ponga n = 1+p₁p₂¼p_t. Poiché |n| ³ 2, esiste un primo p_i che divide n. Ne segue che p_i divide n-p₁p₂¼p_t = 1, un assurdo. ¨

ESERCIZIO 2 Sia m un intero maggiore di 2. Provare che, se m non é divisibile per alcun intero n tale che 2 £ n £ Öm, allora m é primo.

ESERCIZIO 3 Sia m un intero maggiore di 2. Provare che, se m non é divisibile per alcun primo positivo minore o uguale di Öm, allora m é primo.

ESERCIZIO 4 Sia m un intero maggiore di 2 e si consideri la successione Pr(m) di interi costruita con il seguente algoritmo (crivello di Eratostene): 1. scrivere la successione crescente degli interi da 2 ad m;

2. cancellare dalla successione tutti gli interi maggiori di 2 che sono multipli di 2;

3. se nella nuova successione non vi sono interi maggiori di 2 e minori o uguali di Öm terminare l'algoritmo (altrimenti andare al passo successivo);

4. detto p₁ l'intero che compare dopo 2 nella nuova successione (chi é?), cancellare tutti gli interi maggiori di p₁ che sono multipli di p₁;

5. se nella nuova successione non vi sono interi maggiori di p₁ e minori o uguali di Öm terminare l'algoritmo (altrimenti andare al passo successivo);

6. detto p₂ l'intero che compare dopo p₁ nella nuova successione (chi é?), cancellare tutti gli interi maggiori di p₂ che sono multipli di p₂;

....    continuare con la stessa regola fino a quando l'algoritmo termina     .... Provare che Pr(m) é la successione dei numeri primi che sono minori o uguali di m.

OSSERVAZIONE 5 Uno dei problemi piú interessanti che pone il teorema di Euclide é quello di studiare la distribuzione dei numeri primi nell'insieme dei numeri naturali; in altre parole, si tratta di trovare una formula per il numero p(m,n) dei primi p tali che m £ p £ n. La distribuzione molto irregolare dei primi su piccola scala non deve trarre in inganno: é possibile provare che su grande scala questa distribuzione é abbastanza regolare. Per esempio, giá nel diciottesimo secolo, ad opera di Eulero, si sapeva che era divergente la serie degli inversi dei numeri primi

Osserviamo che la successione (p(n) = p(2,n)) é crescente ¹  e che il teorema di Euclide dice che

ESERCIZIO 6 Provare che, per ogni intero n > 1, la successione finita

ESERCIZIO 7 Provare che, se n é un intero maggiore di 1 e p un primo positivo, allora non esiste alcun numero razionale y tale che yⁿ = p.

ESERCIZIO 8 Provare che, se m,n sono interi positivi risulta

OSSERVAZIONE 9 I primi della forma m_p = 2^p-1 si chiamano primi di Mersenne, dal nome di uno dei matematici che li studió. E' aperto il problema di stabilire se esistono o meno infiniti primi di Mersenne. Al momento (febbraio 2002) si conoscono solo trentanove primi di Mersenne (cfr.), precisamente quelli corrispondenti ai seguenti valori di p: 2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107, 127, 521, 607, 1279, 2203, 2281, 3217, 4253, 4423, 9689, 9941, 11213, 19937, 21701, 23209, 44497, 86243, 110503, 132049, 216091, 756839, 859433, 1257787, 1398269, 2976221, 3021377, 6972593, 13466917. L'ultimo di questi é il piú grande numero primo conosciuto ed é stato scoperto il 14 novembre 2001 nell'ambito di un'organizzazione amatoriale di nome GIMPS (The Great Internet Mersenne Prime Search), che si occupa di trovare nuovi primi di Mersenne e puó essere contattata via internet attraverso il seguente indirizzo: http://www.mersenne.org. Su questo sito web si trovano anche molte informazioni sui numeri di Mersenne e, piú in generale, sui numeri primi di forme particolari. ¨

ESERCIZIO 10 Provare che, se 2^h+1 é primo, allora h non puó avere fattori dispari, cioé deve essere una potenza di 2.

OSSERVAZIONE 11 I numeri della successione f_n = (2²ⁿ+1) si chiamano numeri di Fermat, dal nome del matematico che li introdusse. I cinque termini iniziali della successione sono

2.6  Esercizi

1    Provare che, per ogni due interi a,b, risulta

2    Scrivere nelle basi 3,5,8 il numero 358.

3    Scrivere in base 10 i numeri (258)₁₆,(45)₆,(67)₈.

4     Sia a una delle nove cifre decimali diverse da zero. Per ogni intero positivo n, si denoti con k_a(n) il numero degli interi positivi la cui notazione decimale contiene al piú n cifre e, tra queste, la cifra a. Provare che risulta k_a(1) = 1 e, per ogni n > 1,

5    Siano a,b,c interi e si supponga che a,b sono divisori di c. Provare, mediante qualche esempio, che ab non é necessariamente un divisore di c. Provare che, se a,b sono coprimi, allora ab é un divisore di c.

6    Calcolare MCD(18,105) e MCD(205,65).

7    Calcolare il MCD(a²,b³) sapendo che MCD(a,b) = 9.

8    Calcolare il massimo comune divisore positivo d di 140 e 250 e determinare una coppia di interi (a,b) tale che d = 140a + 250b.

9    Provare, usando l'algoritmo di Euclide, che 365 e 3752 sono coprimi.

10    Provare che, per ogni intero n > 1, l'intero n³+1 non é primo.

11    Trovare i numeri primi maggiori di 2 e minori di 100 usando il crivello di Eratostene.

12    Provare che, se a,b sono interi positivi, risulta ab = MCD(a,b)·mcm(a,b).

13    Provare che 5n+3 e 7n+4 sono coprimi per ogni intero non negativo n.

14    Siano a,b interi positivi coprimi. Provare che esistono due interi d,e tali che

2.7  Appendice

2.7.1  Tabella di distribuzione di primi

La tabella che segue riporta alcuni valori noti della funzione p(m,n) pari al numero di primi p con m £ p £ n, m,n interi positivi.

2.7.2  Primi di Mersenne e numeri perfetti

Si chiamano numeri di Mersenne gli interi del del tipo

Al momento si conoscono solo 39 primi p per cui m_p é primo; di seguito ne riportiamo la lista.

E' noto che tra 2 e 1398269 non vi sono altri primi p per cui m_p é primo. Un intero positivo n si dice perfetto se é somma dei suoi divisori positivi propri. Per esempio, i primi due numeri perfetti sono

TEOREMA 1 Un intero positivo n é un numero pari perfetto se, e solo se, n é del tipo 2^p-1(2^p-1), con 2^p-1 primo di Mersenne.

Non é al momento noto se esistano o meno numeri dispari perfetti.

2.7.3  Tabelle di numeri di Fermat

Ricordiamo che si chiamano numeri di Fermat gli interi della successione (cfr.osservazione  11 )

A tutt'oggi si conoscono soltanto i seguenti cinque primi di Fermat:

Si conoscono 151 numeri di Fermat che non sono primi. Le tabelle che seguono riassumono lo stato delle conoscenze attuali sui numeri f_m, con m > 4.

N.B. Il simbolo n_n indica un intero positivo con n cifre decimali.

Note:

¹  Una successione (a_n) di interi si dice crescente se risulta a_n £ a_n+1, per ogni n.

²  Due primi p,q, con p < q, si dicono consecutivi se q é il piú piccolo primo maggiore di p. Nel caso p = 2,q = 3 o q = p+2, i primi p,q si dicono gemelli. Non é noto se l'insieme delle coppie di primi gemelli é finito o infinito. Alcune coppie di primi gemelli sono: (3,5), (5,7), (11,13), (17,19), (29,31), (10.006.427,10.006.429).