Lema de Euclides - Euclid's lemma

Na teoria dos números , o lema de Euclides é um lema que captura uma propriedade fundamental dos números primos , a saber:

Lema de Euclides - Se um primo $p$ divide o produto $ab$ de dois inteiros $de um$ e $b$ , então $p$ deve dividir pelo menos um desses números inteiros $a$ e $b$ .

Por exemplo, se $p = 19$ , $a = 133$ , $b = 143$ , então $ab = 133 \times 143 = 19019$ , e uma vez que isso é divisível por 19, o lema implica que um ou ambos de 133 ou 143 também devem ser. Na verdade, $133 = 19 \times 7$ .

Se a premissa do lema não for válida, isto é, $p$ é um número composto , seu conseqüente pode ser verdadeiro ou falso. Por exemplo, no caso de $p = 10$ , $a = 4$ , $b = 15$ , o número composto 10 divide $ab = 4 \times 15 = 60$ , mas 10 não divide nem 4 nem 15.

Esta propriedade é a chave na prova do teorema fundamental da aritmética . É usado para definir elementos primos , uma generalização de números primos para anéis comutativos arbitrários . O Lema de Euclides mostra que, nos inteiros, os elementos irredutíveis também são elementos primos. A prova usa indução, portanto não se aplica a todos os domínios integrais .

Formulações

Let Ser um número primo , e assume divide o produto de dois inteiros e . Em símbolos, isso está escrito . Sua negação, não divide , está escrita . Então ou (ou ambos). As declarações equivalentes são: ${\ 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 , então . ${\ displaystyle p \ nmid a}$ ${\ displaystyle p \ nmid b}$ ${\ displaystyle p \ nmid ab}$
Se e , então . ${\ displaystyle p \ nmid a}$ ${\ displaystyle p \ mid ab}$ ${\ displaystyle p \ mid b}$

O lema de Euclides pode ser generalizado de números primos para quaisquer inteiros:

Teorema - Se , e é relativamente primo a , então . ${\ displaystyle n \ mid ab}$ ${\ displaystyle n}$ ${\ displaystyle a}$ ${\ displaystyle n \ mid b}$

Esta é uma generalização porque se for primo, qualquer um ${\ displaystyle n}$

${\ displaystyle n \ mid a}$ ou
${\ displaystyle n}$ é relativamente principal para . Nesta segunda possibilidade, então . ${\ displaystyle a}$ ${\ displaystyle n \ nmid a}$ ${\ displaystyle n \ mid b}$

História

O lema aparece pela primeira vez como proposição 30 no Livro VII de Euclides 's Elements . Ele está incluído em praticamente todos os livros que abordam a teoria dos números elementares.

A generalização do lema para inteiros apareceu no livro Nouveaux Elémens de Mathématiques de Jean Prestet em 1681.

No tratado Disquisitiones Arithmeticae de Carl Friedrich Gauss , o enunciado do lema é a Proposição 14 de Euclides (Seção 2), que ele usa para provar a unicidade do produto de decomposição dos fatores primos de um inteiro (Teorema 16), admitindo a existência como "óbvio". Dessa existência e singularidade, ele então deduz a generalização dos números primos para inteiros. Por esta razão, a generalização do lema de Euclides é algumas vezes referida como lema de Gauss, mas alguns acreditam que esse uso é incorreto devido à confusão com o lema de Gauss sobre resíduos quadráticos .

Prova

Prova usando a identidade de Bézout

Na matemática moderna, uma prova comum envolve um resultado denominado identidade de Bézout , que era desconhecido na época de Euclides. A identidade de Bézout afirma que se $x$ e $y$ são números inteiros relativamente primos (ou seja, eles não compartilham divisores comuns além de 1 e -1) existem números inteiros $r$ e $s$ tais que

{\ displaystyle rx + sy = 1.}

Sejam $a$ e $n$ relativamente primos e suponha que $n | ab$ . Pela identidade de Bézout, existem $r$ e $s$ fazendo

{\ displaystyle rn + sa = 1.}

Multiplique ambos os lados por $b$ :

{\ displaystyle rnb + sab = b.}

O primeiro termo à esquerda é divisível por $n$ , e o segundo termo é divisível por $ab$ , que por hipótese é divisível por $n$ . Portanto, sua soma, $b$ , também é divisível por $n$ . Esta é a generalização do lema de Euclides mencionado acima.

Prova direta

A prova a seguir é inspirada na versão de Euclides do algoritmo euclidiano , que prossegue usando apenas subtrações.

Suponha que e . Queremos mostrar isso . Uma vez que há um co - crime $n$ para $a$ (ou seja, seus únicos divisores comuns são $1$ e $-1$ ), de modo que ${\ displaystyle p \ nmid a}$ ${\ displaystyle p \ mid ab}$ ${\ displaystyle p \ mid b}$ ${\ displaystyle p \ nmid a}$

{\ displaystyle nq = ab.}

É preciso provar que $n$ divide $b$ . Para provar isso por indução forte , supomos que isso foi provado para todos os valores inferiores positivos de $ab$ .

Existem três casos:

Se $n = a$ , coprimalidade implica $n = 1$ e $n$ divide $b$ trivialmente.

Se $n < a$ , um tem

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

Os inteiros positivos $a - n$ e $n$ são coprimos: se algum primo divide ambos, então ele divide sua soma e, portanto, divide $n$ e $a$ . Esta é uma contradição da hipótese da coprimalidade. Como consequência do lado direito , $q - b$ é positivo. Assim, a conclusão segue da hipótese de indução, $uma$ vez que $a$ $-$ $n$ $<$ $a$ .

Se $n > a$ , um tem

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

Da mesma forma que acima, $n - a$ e $a$ são coprimos. Como $b - q < b$ , pela hipótese de indução, há um inteiro $r$ tal que So ${\ displaystyle bq = r (na).}$

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

e obtém-se $q = ar$ , dividindo por $n - a$ . Assim e, pela divisão por $a$ , obtém-se $b$ $=$ $nr$ , que é a conclusão desejada. ${\ displaystyle ab = nq = anr,}$

Prova de Elementos

Lema de Euclides é provado na Proposição 30 em livro VII de Euclides Elements . A prova original é difícil de entender como está, então citamos o comentário de Euclid (1956 , pp. 319-332).

Proposição 19: Se quatro números são proporcionais, o número produzido a partir do primeiro e do quarto é igual ao número produzido a partir do segundo e do terceiro; e, se o número produzido do primeiro e do quarto for igual ao produzido do segundo e do terceiro, os quatro números são proporcionais.
Proposição 20: O menor número daqueles que têm a mesma proporção mede aqueles que têm a mesma proporção o mesmo número de vezes - quanto maior, maior, e menor, menos.
Proposição 21: Os números primos entre si são os menores daqueles que têm a mesma proporção com eles.
Proposição 29: Qualquer número primo é primo de qualquer número que não mede.
Proposta 30: Se dois números, multiplicando-se um pelo outro, formam o mesmo número, e qualquer número primo mede o produto, ele também mede um dos números originais.
Prova de 30: Se c , um número primo, meça ab , c mede a ou b .
Suponha que c não mede a .
Portanto , c , a são primos um do outro.［VII. 29］
Suponha ab＝mc .
Portanto, c : a＝b : m . ［VII. 19］
Portanto, ［VII. 20 , 21］b＝nc , onde n é algum número inteiro.
Portanto, c mede b .
Da mesma forma, se c não mede b , c mede a .
Portanto, c mede um ou outro dos dois números a , b .
QED

Veja também

Notas de rodapé

Notas

Citações

Referências

Bajnok, Béla (2013), Um convite para matemática abstrata , Textos de graduação em matemática , Springer, ISBN 978-1-4614-6636-9.
Euclid (1956), The Thirteen Books of the Elements , vol. 2 (Livros III-IX), traduzido por Heath, Thomas Little , Dover Publications, ISBN 978-0-486-60089-5 |volume=tem texto extra ( ajuda )- vol. 2
Euclid (1994), Les Éléments, traduction, commentaires et notes (em francês), 2 , traduzido por Vitrac, Bernard, pp. 338-339, ISBN 2-13-045568-9
Gauss, Carl Friedrich (2001), Disquisitiones Arithmeticae , traduzido por Clarke, Arthur A. (Segunda edição corrigida), New Haven, CT: Yale University Press, ISBN 978-0-300-09473-2
Gauss, Carl Friedrich (1981), Untersuchungen uber hohere Arithmetik [ Investigations on upper arithmetic ], traduzido por Maser, = H. (Second ed.), New York: Chelsea, ISBN 978-0-8284-0191-3
Hardy, GH ; Wright, EM ; Wiles, AJ (2008-09-15), Uma Introdução à Teoria dos Números (6ª ed.), Oxford: Oxford University Press , ISBN 978-0-19-921986-5
Irlanda, Kenneth; Rosen, Michael (2010), A Classical Introduction to Modern Number Theory (segunda edição), New York: Springer , ISBN 978-1-4419-3094-1
Joyner, David; Kreminski, Richard; Turisco, Joann (2004), Applied Abstract Algebra , JHU Press, ISBN 978-0-8018-7822-0.
Landau, Edmund ; Goodman, JE (tradutor para inglês) (1999), Elementary Number Theory (2ª ed.), Providence, Rhode Island: American Mathematical Society, ISBN 978-0-821-82004-9
Martin, GE (2012), The Foundations of Geometry and the Non-Euclidean Plane , Undergraduate Texts in Mathematics, Springer, ISBN 978-1-4612-5725-7.
Riesel, Hans (1994), Prime Numbers and Computer Methods for Factorization (2ª ed.), Boston: Birkhäuser, ISBN 978-0-8176-3743-9.

links externos

Weisstein, Eric W. "Euclid's Lemma" . MathWorld .

Languages

In other projects