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.

Sia p un fattore primo di ab e si supponga che non sia un divisore di a. Allora ${\displaystyle 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 ${\displaystyle 1=px+ay}$. Moltiplicando per b entrambi i membri:

${\displaystyle b=b(px+ay)}$

${\displaystyle b=bpx+bay.}$

Ricordando che ${\displaystyle rp=ab}$, segue:

${\displaystyle b=bpx+rpy}$

${\displaystyle 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.

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.

• 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.

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

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

V · D · M Teoria dei numeri
Numeri più usati	Naturali · Interi · Pari e dispari
Principi generali	Principio d'induzione · Principio del buon ordinamento · Relazione di equivalenza
Successioni di interi	Fattoriale · Successione di Fibonacci · Numero di Catalan · Numero di Perrin · Numero di Eulero · Successione di Mian-Chowla · Successione di Thue-Morse
Caratteristiche dei numeri primi	Numero primo · Lemma di Euclide · Teorema dell'infinità dei numeri primi · Crivello di Eratostene · Test di primalità · Teorema fondamentale dell'aritmetica · Interi coprimi · Identità di Bézout · MCD · mcm · Algoritmo di Euclide · Algoritmo esteso di Euclide · Teorema dei numeri primi
Funzioni aritmetiche	Funzione moltiplicativa · Funzione additiva · Convoluzione di Dirichlet · Funzione φ di Eulero · Funzione di Möbius · Funzione tau sui positivi · Funzione sigma · Funzione di Liouville · Funzione di Mertens
Aritmetica modulare	Teorema cinese del resto · Piccolo teorema di Fermat · Teorema di Eulero · Criteri di divisibilità · Teorema di Fermat sulle somme di due quadrati · Teorema di Wilson · Legge di reciprocità quadratica
Congetture	Congettura di Goldbach · Congettura di Polignac · Congettura abc · Congettura dei numeri primi gemelli · Congettura di Legendre · Nuova congettura di Mersenne · Congettura di Collatz · Ipotesi di Riemann
Altro	Problema di Waring
Principali teorici	Fibonacci · Fermat · Gauss · Eulero · Legendre · Riemann · Dirichlet
Discipline connesse	Teoria algebrica dei numeri · Teoria analitica dei numeri · Crittografia · Teoria computazionale dei numeri

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