Lemma di Euclide - Euclid's lemma

In teoria dei numeri , il lemma di Euclide è un lemma che cattura una proprietà fondamentale dei numeri primi , ovvero:

Ad esempio, se p = 19 , a = 133 , b = 143 , allora ab = 133 × 143 = 19019 , e poiché questo è divisibile per 19, il lemma implica che anche uno o entrambi di 133 o 143 debbano esserlo. Infatti, 133 = 19 × 7 .

Se non vale la premessa del lemma, cioè p è un numero composto , il suo conseguente può essere vero o falso. Ad esempio, nel caso di p = 10 , a = 4 , b = 15 , il numero composto 10 divide ab = 4 × 15 = 60 , ma 10 non divide né 4 né 15.

Questa proprietà è la chiave nella dimostrazione del teorema fondamentale dell'aritmetica . È usato per definire gli elementi primi , una generalizzazione dei numeri primi ad anelli commutativi arbitrari . Il Lemma di Euclide mostra che negli interi gli elementi irriducibili sono anche elementi primi. La dimostrazione usa l' induzione quindi non si applica a tutti i domini integrali .

formulazioni

Sia un numero primo , e supponiamo che divida il prodotto di due interi e . In simboli, questo è scritto . La sua negazione, non divide , è scritta . Allora o (o entrambi). Dichiarazioni equivalenti sono: ${\displaystyle p}$${\displaystyle p}$${\displaystyle a}$${\displaystyle b}$${\displaystyle p\mid ab}$${\displaystyle p}$${\displaystyle ab}$${\displaystyle p\nmid ab}$${\displaystyle p\mid a}$${\displaystyle p\mid b}$

• Se e , allora .${\displaystyle p\nmid a}$${\displaystyle p\nmid b}$${\displaystyle p\nmid ab}$
• Se e , allora .${\displaystyle p\nmid a}$${\displaystyle p\mid ab}$${\displaystyle p\mid b}$

Il lemma di Euclide può essere generalizzato dai numeri primi a qualsiasi numero intero:

Questa è una generalizzazione perché se è primo, sia ${\displaystyle n}$

• ${\displaystyle n\mid a}$ o
• ${\displaystyle n}$è relativamente primo a . In questa seconda possibilità, così .${\displaystyle a}$${\displaystyle n\nmid a}$${\displaystyle n\mid b}$

Storia

Il lemma prima appare come proposizione 30 nel libro VII di Euclide 's elementi . È incluso praticamente in tutti i libri che trattano la teoria elementare dei numeri.

La generalizzazione del lemma agli interi apparve nel libro di testo di Jean Prestet Nouveaux Elémens de Mathématiques nel 1681.

Nel trattato Disquisitiones Arithmeticae di Carl Friedrich Gauss , l'enunciato del lemma è la Proposizione 14 di Euclide (Sezione 2), che usa per dimostrare l'unicità del prodotto di scomposizione dei fattori primi di un intero (Teorema 16), ammettendo l'esistenza come "ovvio". Da questa esistenza e unicità deduce poi la generalizzazione dei numeri primi agli interi. Per questo motivo, la generalizzazione del lemma di Euclide è talvolta indicata come lemma di Gauss, ma alcuni ritengono che questo utilizzo non sia corretto a causa della confusione con il lemma di Gauss sui residui quadratici .

Prova

Prova usando l'identità di Bézout

Nella matematica moderna, una dimostrazione comune implica un risultato chiamato identità di Bézout , che era sconosciuto ai tempi di Euclide. Di Bézout identità afferma che se x ed y sono primi numeri interi (cioè condividono senza divisori comuni diversi da 1 e -1) esistono interi r e s tale che

${\displaystyle rx+sy=1.}$

Siano a e n primi relativamente, e assumiamo che n | ab . Per l'identità di Bézout, ci sono r e s making

${\displaystyle rn+sa=1.}$

Moltiplica entrambi i membri per b :

${\displaystyle rnb+sab=b.}$

Il primo termine a sinistra è divisibile per n , e il secondo termine è divisibile per ab , che per ipotesi è divisibile per n . Quindi anche la loro somma, b , è divisibile per n . Questa è la generalizzazione del lemma di Euclide menzionato sopra.

Prova diretta

La seguente dimostrazione è ispirata alla versione di Euclide dell'algoritmo euclideo , che procede utilizzando solo sottrazioni.

Supponiamo che e . Vogliamo dimostrarlo . Poiché , esiste un n coprimo ad a (cioè i loro unici divisori comuni sono 1 e –1 ) tale che ${\displaystyle p\nmid a}$${\displaystyle p\mid ab}$${\displaystyle p\mid b}$${\displaystyle p\nmid a}$

${\displaystyle nq=ab.}$

Si deve dimostrare che n divide b . Per dimostrare questo per induzione forte , supponiamo che questo sia stato dimostrato per tutti i valori inferiori positivi di ab .

Ci sono tre casi:

Se n = a , la coprimalità implica n = 1 e n divide b banalmente.

Se n < a , si ha

${\displaystyle n(qb)=(an)b.}$

Gli interi positivi a – n e n sono coprimi: se un numero primo divide entrambi, allora divide la loro somma, e quindi divide sia n che a . Questa è una contraddizione dell'ipotesi di coprimità. Come conseguenza del membro destro , q – b è positivo. Quindi, la conclusione segue dall'ipotesi di induzione, poiché a – n < a .

Se n > a , si ha

${\displaystyle (na)q=a(bq).}$

Allo stesso modo come sopra, n - a e a sono coprimi. Poiché b – q < b , per l'ipotesi di induzione, esiste un intero r tale che So ${\displaystyle bq=r(na).}$

${\displaystyle (na)q=a(bq)=ar(na),}$

e si ottiene q = ar , dividendo per n – a . Quindi e, dividendo per a , si ottiene b = nr , che è la conclusione desiderata. ${\displaystyle ab=nq=anr,}$

Dimostrazione degli elementi

Il lemma di Euclide è dimostrato dalla Proposizione 30 nel Libro VII degli Elementi di Euclide . La dimostrazione originale è difficile da capire così com'è, quindi citiamo il commento di Euclide (1956 , pp. 319-332).

Proposta 19

Se quattro numeri sono proporzionali, il numero prodotto dal primo e dal quarto è uguale al numero prodotto dal secondo e dal terzo; e se il numero prodotto dal primo e dal quarto è uguale a quello prodotto dal secondo e dal terzo, i quattro numeri sono proporzionali.

Proposta 20

Il numero minimo di quelli che hanno lo stesso rapporto con loro misura quelli che hanno lo stesso rapporto lo stesso numero di volte: maggiore è il maggiore e minore è il minore.

Proposta 21

I numeri primi tra loro sono i minimi di quelli che hanno lo stesso rapporto con loro.

Proposta 29

Qualsiasi numero primo è primo rispetto a qualsiasi numero che non misura.

Proposta 30

Se due numeri, moltiplicandosi tra loro, fanno lo stesso numero, e un qualsiasi numero primo misura il prodotto, misura anche uno dei numeri originari.

Prova di 30

Se c , un numero primo, misura ab , c misura a o b .
Supponiamo che c non misuri a .
Quindi c , a sono primi tra loro.[ VII. 29 giorni
Supponiamo che ab = mc .
Quindi c  : a＝b : m . [ VII. 19 ]
Quindi ［VII. 20 , 21］b＝nc , dove n è un numero intero.
Quindi c misura b .
Allo stesso modo, se c non misura b , c misura a .
Quindi c misura l'uno o l'altro dei due numeri a , b .
QED

Guarda anche

Note a piè di pagina

Appunti

citazioni

Riferimenti

• Bajnok, Béla (2013), Un invito alla matematica astratta , Testi universitari in matematica , Springer, ISBN 978-1-4614-6636-9.
• Euclide (1956), I tredici libri degli elementi , vol. 2 (Libri III-IX), tradotto da Heath, Thomas Little , Dover Publications, ISBN 978-0-486-60089-5 |volume=ha del testo extra ( aiuto )- vol. 2
• Euclid (1994), Les Éléments, traduzione, commenti e note (in francese), 2 , tradotto da Vitrac, Bernard, pp. 338-339, ISBN 2-13-045568-9
• Gauss, Carl Friedrich (2001), Disquisitiones Arithmeticae , tradotto da Clarke, Arthur A. (Secondo, corretto ed.), New Haven, CT: Yale University Press, ISBN 978-0-300-09473-2
• Gauss, Carl Friedrich (1981), Untersuchungen uber hohere Arithmetik [ Indagini sull'aritmetica superiore ], tradotto da Maser, = H. (Seconda ed.), New York: Chelsea, ISBN 978-0-8284-0191-3
• Hardy, GH ; Wright, EM ; Wiles, AJ (2008-09-15), Introduzione alla teoria dei numeri (6a ed.), Oxford: Oxford University Press , ISBN 978-0-19-921986-5
• Irlanda, Kenneth; Rosen, Michael (2010), A Classical Introduction to Modern Number Theory (seconda ed.), New York: Springer , ISBN 978-1-4419-3094-1
• Joyner, David; Creminski, Riccardo; Turisco, Joann (2004), Algebra astratta applicata , JHU Press, ISBN 978-0-8018-7822-0.
• Landau, Edmund ; Goodman, JE (traduttore in inglese) (1999), Elementary Number Theory (2a ed.), Providence, Rhode Island: American Mathematical Society, ISBN 978-0-821-82004-9
• Martin, GE (2012), I fondamenti della geometria e il piano non euclideo , Testi universitari in matematica, Springer, ISBN 978-1-4612-5725-7.
• Riesel, Hans (1994), Numeri primi e metodi informatici per la fattorizzazione (2a ed.), Boston: Birkhäuser, ISBN 978-0-8176-3743-9.

link esterno

• Weisstein, Eric W. "Lemma di Euclide" . MathWorld .