Lemma di Euclide

Da Wikipedia, l'enciclopedia libera.

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(na) = 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[modifica | modifica sorgente]

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[modifica | modifica sorgente]

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[modifica | modifica sorgente]

  • 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[modifica | modifica sorgente]

matematica Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica