Lemma di Euclide

Il lemma di Euclide è una generalizzazione della Proposizione 30 del Libro VII degli Elementi di Euclide. Il lemma afferma che

Se un numero n, intero positivo, divide il prodotto di due numeri a e b, interi positivi, ed è coprimo con uno dei due (es. a), allora è divisore dell'altro (es. b).

Utilizzando le usuali notazioni matematiche, ciò si può scrivere come segue:

Se n|ab e MCD(n, a) = 1 allora n|b.

La Proposizione 30, nota anche come primo teorema di Euclide, afferma:

Se un numero primo divide il prodotto di due interi positivi, allora il numero primo divide almeno uno dei due interi positivi.

Ciò si può scrivere come:

Se p|ab allora p|a oppure p|b.

Naturalmente, questo risultato si può dedurre immediatamente dal lemma di Euclide, in quanto un numero primo è coprimo con un numero intero se e solo se non lo divide.

Spesso la Proposizione 30 viene chiamata lemma di Euclide in luogo della generalizzazione sopra citata. Un'applicazione molto comune del lemma di Euclide nei libri di testo di matematica è la dimostrazione del teorema fondamentale dell'aritmetica che, peraltro, può essere dimostrato senza farne uso.

Dimostrazione della Proposizione 30

Sia p un fattore primo di ab e si supponga che non sia un divisore di a. Allora $rp=ab$ per un opportuno intero r. Dal momento che p è primo e non divide a, a e p sono coprimi. Pertanto, per l'identità di Bézout esistono due interi x ed y tali che $1=px+ay$. Moltiplicando per b entrambi i membri:

$b=b(px+ay)$

$b=bpx+bay.$

Ricordando che $rp=ab$, segue:

$b=bpx+rpy$

$b=p(bx+ry).$

Di conseguenza, p è un divisore di b. Quindi p divide necessariamente a oppure b (o entrambi). Q.E.D.

La stessa dimostrazione si adatta facilmente per il lemma più generale.

Esempio

Sia N = 42 e p = 7. Poiché 42 = 7·6, 7 divide 42. Osservando che, ad esempio, N = 3·14, per il lemma di Euclide deve verificarsi necessariamente che 7 divide 14 oppure che 7 divide 3. In questo caso è evidentemente vera la prima relazione, essendo 14 = 7·2.

Bibliografia

• Trygve Nagell, Introduction to number theory, 2ª ed., New York, Chelsea, 2001, ISBN 0-8218-2833-9.
• Tom M. Apostol, Introduction to Analytic Number Theory, New York, Springer-Verlag, 1976, ISBN 0-387-90163-9.

Voci correlate

• Algoritmo di Euclide
• Identità di Bézout
• Teorema fondamentale dell'aritmetica

Collegamenti esterni

• (EN) Eric W. Weisstein, Lemma di Euclide, su MathWorld, Wolfram Research.