Lema de Euclides - Euclid's lemma
En teoría de números , el lema de Euclides es un lema que captura una propiedad fundamental de los números primos , a saber:
Lema de Euclides - Si de un primo p divide el producto ab de dos enteros a y b , entonces p debe dividir al menos uno de esos números enteros una y b .
Por ejemplo, si p = 19 , a = 133 , b = 143 , entonces ab = 133 × 143 = 19019 , y dado que esto es divisible por 19, el lema implica que uno o ambos de 133 o 143 también deben serlo. De hecho, 133 = 19 × 7 .
Si la premisa del lema no se cumple, es decir, p es un número compuesto , su consecuente puede ser verdadero o falso. Por ejemplo, en el caso de p = 10 , a = 4 , b = 15 , el número compuesto 10 divide ab = 4 × 15 = 60 , pero 10 no divide ni a 4 ni a 15.
Esta propiedad es la clave en la demostración del teorema fundamental de la aritmética . Se utiliza para definir elementos primos , una generalización de números primos a anillos conmutativos arbitrarios . El Lema de Euclides muestra que en los números enteros los elementos irreductibles también son elementos primos. La prueba usa inducción, por lo que no se aplica a todos los dominios integrales .
Formulaciones
Sea un número primo y suponga que divide el producto de dos enteros y . En símbolos, esto está escrito . Su negación, no divide , está escrita . Entonces o (o ambos). Las declaraciones equivalentes son:
- Si y , entonces .
- Si y , entonces .
El lema de Euclides se puede generalizar a partir de números primos a cualquier número entero:
Teorema - Si , y es primo con respecto a , a continuación .
Esta es una generalización porque si es primo, o
- o
- es relativamente primordial para . En esta segunda posibilidad, entonces .
Historia
El lema aparece por primera vez como proposición 30 en el Libro VII de los Elementos de Euclides . Está incluido en prácticamente todos los libros que cubren la teoría de números elemental.
La generalización del lema a números enteros apareció en el libro de texto Nouveaux Elémens de Mathématiques de Jean Prestet en 1681.
En el tratado Disquisitiones Arithmeticae de Carl Friedrich Gauss , el enunciado del lema es la Proposición 14 de Euclides (Sección 2), que usa para probar la unicidad del producto de descomposición de los factores primos de un número entero (Teorema 16), admitiendo la existencia como "obvio". De esta existencia y unicidad deduce la generalización de números primos a enteros. Por esta razón, la generalización del lema de Euclides a veces se denomina lema de Gauss, pero algunos creen que este uso es incorrecto debido a la confusión con el lema de Gauss sobre residuos cuadráticos .
Prueba
Prueba con la identidad de Bézout
En las matemáticas modernas, una prueba común implica un resultado llamado identidad de Bézout , que era desconocido en la época de Euclides. Estados de identidad de Bézout que si x y y son enteros primos relativos (es decir, que comparten no hay divisores comunes distintos de 1 y -1) existen enteros r y s tal que
Deje una y n ser primos entre sí, y se supone que n | ab . Por la identidad de Bézout, hay r y s decisiones
Multiplica ambos lados por b :
El primer término de la izquierda es divisible por n , y el segundo término es divisible por ab , que por hipótesis es divisible por n . Por lo tanto, su suma, b , también es divisible por n . Ésta es la generalización del lema de Euclides mencionado anteriormente.
Prueba directa
La siguiente prueba está inspirada en la versión de Euclides del algoritmo euclidiano , que procede utilizando solo restas.
Supongamos que y . Queremos mostrar eso . Desde , hay un n primos entre sí a una (es decir, sus divisores solamente comunes son 1 y -1 ) tal que
Hay que demostrar que n divide a b . Para probar esto por inducción fuerte , suponemos que esto ha sido probado para todos los valores inferiores positivos de ab .
Hay tres casos:
Si n = a , la coprimalidad implica n = 1 , y n divide b trivialmente.
Si n < a , uno tiene
Los enteros positivos a - n y n son coprimos: si un número primo divide a ambos, entonces divide su suma y, por lo tanto, divide tanto n como a . Esta es una contradicción de la hipótesis de la coprimalidad. Como consecuencia del lado derecho , q - b es positivo. Entonces, la conclusión se deriva de la hipótesis de inducción, ya que a - n < a .
Si n > a , uno tiene
Del mismo modo que anteriormente, n - una y una son primos entre sí. Dado que b - q < b , según la hipótesis de inducción, hay un entero r tal que Entonces
y se obtiene q = ar , dividiendo por n - a . Así y, por división por a , se obtiene b = nr , que es la conclusión deseada.
Prueba de elementos
El lema de Euclides se prueba en la Proposición 30 del Libro VII de los Elementos de Euclides . La prueba original es difícil de entender tal como está, por lo que citamos el comentario de Euclides (1956 , págs. 319-332).
- Proposición 19
- Si cuatro números son proporcionales, el número producido por el primero y el cuarto es igual al número producido por el segundo y el tercero; y, si el número producido por el primero y el cuarto es igual al producido por el segundo y el tercero, los cuatro números son proporcionales.
- Proposición 20
- El menor número de los que tienen la misma proporción mide los que tienen la misma proporción el mismo número de veces: cuanto mayor es mayor y menor, menor.
- Proposición 21
- Los números primos entre sí son los menores de los que tienen la misma proporción.
- Proposición 29
- Cualquier número primo es primo de cualquier número que no mida.
- Proposición 30
- Si dos números, al multiplicarse entre sí, forman el mismo número, y cualquier número primo mide el producto, también mide uno de los números originales.
- Prueba de 30
- Si c , un número primo, mide ab , c mide a o b .
Suponga que c no mide a .
Por lo tanto , c , a son primos entre sí.[VII. 29]
Suponga ab=mc .
Por lo tanto c : a=b : m . [VII. 19]
De ahí [VII. 20 , 21]b=nc , donde n es un número entero.
Por lo tanto c mide b .
De manera similar, si c no mide b , c mide a .
Por lo tanto, c mide uno u otro de los dos números a , b .
QED
Ver también
Notas al pie
Notas
Citas
Referencias
- Bajnok, Béla (2013), Una invitación a las matemáticas abstractas , Textos de pregrado en matemáticas , Springer, ISBN 978-1-4614-6636-9.
-
Euclides (1956), Los trece libros de los elementos , vol. 2 (Libros III-IX), traducido por Heath, Thomas Little , Dover Publications, ISBN 978-0-486-60089-5
|volume=
tiene texto extra ( ayuda )- vol. 2 - Euclid (1994), Les Éléments, traducción, commentaires et notes (en francés), 2 , traducido por Vitrac, Bernard, págs. 338–339, ISBN 2-13-045568-9
- Gauss, Carl Friedrich (2001), Disquisitiones Arithmeticae , traducido por Clarke, Arthur A. (Segunda edición corregida), New Haven, CT: Yale University Press, ISBN 978-0-300-09473-2
- Gauss, Carl Friedrich (1981), Untersuchungen uber hohere Arithmetik [ Investigaciones sobre aritmética superior ], traducido por Maser, = H. (Segunda ed.), Nueva York: Chelsea, ISBN 978-0-8284-0191-3
- Hardy, GH ; Wright, EM ; Wiles, AJ (2008-09-15), Introducción a la teoría de los números (6a ed.), Oxford: Oxford University Press , ISBN 978-0-19-921986-5
- Irlanda, Kenneth; Rosen, Michael (2010), A Classical Introduction to Modern Number Theory (Segunda ed.), Nueva York: Springer , ISBN 978-1-4419-3094-1
- Joyner, David; Kreminski, Richard; Turisco, Joann (2004), Álgebra abstracta aplicada , JHU Press, ISBN 978-0-8018-7822-0.
- Landau, Edmund ; Goodman, JE (traductor al inglés) (1999), Elementary Number Theory (2a ed.), Providence, Rhode Island: American Mathematical Society, ISBN 978-0-821-82004-9
- Martin, GE (2012), Los fundamentos de la geometría y el plano no euclidiano , Textos de pregrado en matemáticas, Springer, ISBN 978-1-4612-5725-7.
- Riesel, Hans (1994), Números primos y métodos informáticos para la factorización (2a ed.), Boston: Birkhäuser, ISBN 978-0-8176-3743-9.