Ritorno
ai numeri primiSi tratta quindi di dimostrare:
Teorema 1: Ogni numero naturale n >1 si esprime in modo unico come un prodotto di numeri primi.
Mostriamo prima alcuni risultati preliminari (i cosiddetti "lemmi"):
Lemma 2: Ogni numero naturale n >1 é divisibile per un numero primo.
Dim: Se n é primo allora n = 1.n, quindi n é divisibile per il numero primo n. Se n non é primo, per definizione, n é divisibile per un numero, n
1 con 1 < n1 < n: n = cn1. Osserviamo che n1 < n. Se n1 é primo, abbiamo finito. Altrimenti n1 é divisibile per un numero, n2, con 1 < n2 < n1: n1 = b.n2. Osserviamo che n > n1 > n2 > 1. Questo processo non può continuare indefinitamente perché tra n e 1 c'é solo un numero finito di numeri naturali perciò ad un certo punto otteremo un numero nk primo, e il lemma é dimostrato.
Lemma 3: Ogni numero naturale n > 1 é un prodotto di numeri primi.
Dim: E' una conseguenza del lemma precedente: per il lemma 1, n é divisibile per un numero primo p
1: n = p1n1. Se n1 é primo abbiamo finito. Altrimenti, per il lemma 1, anche n1 é divisibile per un numero primo: n1 = p2n2. Abbiamo quindi: n = p1p2n2. Se n2 é primo abbiamo finito; altrimenti andiamo avanti con n2. Questo procedimento avrà fine perché n > n1 > n2 >...> 1. Si capiterà quindi su nk = pk numero primo e si avrà n = p1.p2...pk.Questo lemma mostra l'esistenza di una decomposizione in fattori primi, adesso bisogna dimostrare che questa decomposizione é unica. Ci servono altri preliminari.
Il più grande comune divisore di due numeri naturali m, n si nota (m,n).
Quindi se d = (m,n) abbiamo d divide m e d divide n; inoltre per ogni v tale che v divide m e v divide n, si ha v <= d. Per esempio (4,6) = 2 mentre (3,5) = 1.
Due numeri naturali sono primi tra di loro se hanno come unico fattore in comune 1. Questo é equivalente a: (m,n) = 1. Per esempio 4 e 5 sono primi tra di loro.
Teorema 4: Siano a,b due numeri naturali se d = (a,b) allora esistono dei numeri interi (positivi o negativi) u, v tali che: au + bv = d.
Questo é il teorema di Bezout (1730-1783), per dimostrarlo useremo due fatti di facile comprensione intuitiva ma che sono alla base della struttura dei numeri interi. Il primo é la divisione euclidea:
Sia n un numero naturale e t un numero intero (positivo o negativo) allora esistono degli interi q, r tali che: t = dq + r con 0 = r < d. Si può dimostrare l'unicità della coppia (q,r) ma non useremo questo fatto.
Forse conoscete la divisione euclidea se t é positivo. In questo caso é facile concludere: -t = qd + r quindi t = -qd-r; se r =0 abbiamo finito altrimenti: t = (-q-1)d + (d-r) e 0 < (d-r) < d.
Il secondo fatto che useremo (in qualche modo l'abbiamo già usato nelle dimostrazioni precedenti) é che ogni sottinsieme (non vuoto), A, dell'insieme dei numeri naturali possiede un più piccolo elemento. In altre parole esiste a in A tale che per ogni elemento b di A: b >= a.
Osserviamo che l'analoga proprietà non è vera per l'insieme dei numeri reali: sia A l'insieme degli 1/x dove x é un numero reale strettamente positivo; se x > 0 allora 1/2x < 1/x quindi A non ammette un più piccolo elemento.
Dimostrazione del teorema 4: Sia A l'insieme dei numeri interi della forma ax+by dove x, y sono numeri interi qualsiasi. Sia A+ l'insieme degli ax+by che sono strettamente positivi. Osserviamo che a = a.1+b.0, b = a.0+b.1 quindi a e b sono in A+. Sia d il più piccolo elemento di A+. Essendo d un elemento di A abbiamo d = au+bv per degli interi u,v. Per concludere ci basta far vedere che (a,b) = d.
Mostriamo che ogni elemento di A é un multiplo di d. Sia t in A e t = qd+r, 0 <= r < d la divisione euclidea di t per d. Siccome t é in A abbiamo t = az+bw da cui: t - qd = a(z-qu)+b(w-qv) = r. Quindi anche r appartiene ad A ma: 0 <= r < d, e d é il più piccolo elemento di A+. L'unica possibilità é r = 0 pertanto t = qd. Abbiamo dimostrato che ogni elemento di A é un multiplo di d. In particolare d divide a e d divide b. Finalmente sia k > 0 che divide a e divide b, dalla scrittura d = au+bv segue che k divide d quindi k <= d. Questo conclude la dimostrazione dell'uguaglianza (a,b) = d e del teorema 4.
Lemma 5: (Gauss) Sia p un numero primo e a,b dei numeri naturali.Se p divide ab allora p divide a o p divide b.
Dim: Abbiamo (a,p) = p o 1 perché gli unici divisori di p sono 1 e p. Se (a,p) = p allora p divide a. Se (a,p) = 1 dal teorema di Bezout esistono degli interi u, v tali che au+pv = 1. Moltiplicando per b: abu+bpv = b. Osserviamo che p divide il primo membro di questa uguaglianza (p divide ab per ipotesi) perciò p divide anche il secondo ossia p divide b.
Finalmente possiamo dimostrare il teorema 1: supponiamo di avere due decomposizioni:
n = p1...pk = q1...qm (*) (i pi e i qj sono dei numeri primi ma non necessariamente distinti). Osservare che non sappiamo, a priori, che k = m, supponiamo k <= m. Da (*) segue che p1 divide q1...qm. Dal lemma 5, p1 divide uno dei qj, siccome qj é primo abbiamo p1 = qj (gli unici divisori di qj sono 1 e qj). Riordinando gli indici possiamo suppore j = 1 ossia q1 = p1. Adesso da (*) viene: p2...pk = q2...qm (*'). Procediamo come prima ma questa volta con p2; e poi con p3 ecc...fino ad arrivare ad un'espressione del tipo 1 = qk+1...qm; ma questo é assurdo (ogni qj é > 1); quindi k = m e qi = pi per ogni i.
Il teorema é dimostrato.
Ritorno
ai numeri primi
