Lema de Euclides

format_list_bulleted Contenido keyboard_arrow_down

ImprimirCitar

En álgebra y teoría de números, el lema de Euclides es un lema que captura una propiedad fundamental de los números primos, a saber:

Euclid's lemma—Si un primo $p$ divide el producto $ab$ de dos enteros $a$ y $b$ Entonces $p$ debe dividir al menos uno de esos enteros $a$ o $b$ .

Por ejemplo, si $p = 19$ , $a = 133, b = 143, luego ab = 133 \times 143 = 19019< /span>, 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 \times 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 \times 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 irreducibles también son elementos primos. La prueba utiliza inducción, por lo que no se aplica a todos los dominios integrales.

Formulaciones

El lema de Euclides se utiliza comúnmente en la siguiente forma equivalente:

Theorem—Si ${displaystyle p}$ es un número primo que divide el producto ${displaystyle ab}$ y no divide ${displaystyle a,}$ entonces se divide ${displaystyle b.}$

El lema de Euclides se puede generalizar de la siguiente manera, desde números primos hasta cualquier número entero.

Theorem—Si un entero $n$ divide el producto $ab$ de dos enteros, y es coprime con $a$ Entonces $n$ divideciones $b$ .

Esto es una generalización porque un número primo $p$ es coprimo con un número entero $a$ si y sólo si $p$ no divide $a$ .

Historia

La lema aparece primero como propuesta 30 en el libro VII de Euclides Elementos. Está incluido en prácticamente todos los libros que cubren la teoría del número primario.

La generalización de la lema a los enteros apareció en el libro de texto de Jean Prestet Nouveaux Elémens de Mathématiques en 1681.

En el tratado de Carl Friedrich Gauss Disquisitiones Arithmeticae, el enunciado del lema es la Proposición 14 de Euclides (Sección 2), que utiliza para demostrar la unicidad de la descomposición. producto de factores primos de un número entero (Teorema 16), admitiendo la existencia como "obvia". De esta existencia y unicidad deduce luego la generalización de los números primos a números 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.

Pruebas

Las dos primeras subsecciones son pruebas de la versión generalizada del lema de Euclides, a saber, que: if $n< /span> divide ab y es coprimo con a luego divide b .$

El lema original de Euclides se sigue inmediatamente, ya que, si $n$ es primo, entonces divide a $a$ o no divide $a$ en el cual En este caso, es coprimo con $a$ , por lo que, según la versión generalizada, divide $b$ .

Usando la identidad de Bézout

En las matemáticas modernas, una prueba común implica la identidad de Bézout, que era desconocida en la época de Euclides. La identidad de Bézout establece que si $x$ y $y$ son números enteros coprimos (es decir, no comparten divisores comunes distintos de 1 y −1). Existen números enteros $r$ y $< es$ tal que

{displaystyle rx+sy=1.}

Sean $a$ y $n$ coprimos y supongamos que ese $n | ab$ . Según la identidad de Bézout, hay $r$ y $s$ tal que

{displaystyle rn+sa=1.}

Multiplica ambos lados por $b$ :

{displaystyle rnb+sab=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$ .

Por inducción

La siguiente prueba está inspirada en la versión de Euclides del algoritmo euclidiano, que procede utilizando únicamente restas.

Supongamos que ${displaystyle nmid ab}$ y eso $n$ y $a$ son coprime (es decir, su mayor divisor común es $1$ ). Uno tiene que probar que $n$ divideciones $b$ . Desde ${displaystyle nmid ab,}$ hay un entero $q$ tales que ${displaystyle nq=ab.}$ Sin pérdida de generalidad, se puede suponer que $n$ , $q$ , $a$ , y $b$ son positivos, ya que la relación divisibilidad es independiente de los signos de los enteros involucrados.

Para demostrar esto mediante inducción fuerte, suponemos que el resultado se ha demostrado para todos los valores inferiores positivos de $ab$ .

Hay tres casos:

Si $n = a$ , coprimalidad implica $n = 1$ , y $n$ divide $b$ trivialmente.

Si $n < a$ , uno tiene

{displaystyle n(q-b)=(a-n)b.}

Los enteros positivos $a - n$ y $n$ son coprimos: su máximo común divisor $d$ debe dividir su suma y, por lo tanto, divide a ambos. $n$ y $a$ . Resulta que $d = 1$ , según la hipótesis de coprimalidad. Entonces, la conclusión se deriva de la hipótesis de inducción, ya que $0 < (a - n) b < ab$ .

Del mismo modo, si $n > un$ uno tiene

{displaystyle (n-a)q=a(b-q),}

y el mismo argumento muestra que $n - a$ y $a$ son coprime. Por lo tanto, uno tiene $0 a () b - q) ab$ , y la hipótesis de inducción implica que $n - a$ divideciones $b - q$ ; es decir, ${displaystyle b-q=r(n-a)}$ para un entero. Entonces, ${displaystyle (n-a)q=ar(n-a),}$ y, dividiendo $n - a$ , uno tiene ${displaystyle q=ar.}$ Por lo tanto, ${displaystyle ab=nq=anr,}$ y dividiendo $a$ , uno se pone ${displaystyle b=nr,}$ el resultado deseado.

Prueba de los elementos

El lema de Euclides se demuestra 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 de la primera y la cuarta es igual al número producido de la segunda y tercera; y, si el número producido de la primera y la cuarta es igual al producido de la segunda y tercera, los cuatro números son proporcionales.
Proposición 20: El menor número de los que tienen la misma relación con ellos mide a los que tienen la misma relación el mismo número de veces, tanto mayor como menor.
Proposición 21: Los números primos unos a otros son los menos de los que tienen la misma relación con ellos.
Proposición 29: Cualquier número primo es primo a cualquier número que no mida.
Proposición 30: Si dos números, multiplicando el uno al otro, hacen 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, medida ab, c medidas o a o b.
Suppose c no mide a.
Por lo tanto c, a son primos unos a otros. [VII. 29]
Suppose ab=mc.
Por lo tanto c: a = b : m. [VII. 19]
Por lo tanto [VII. 20, 21] b=nc, donde n es un entero.
Por lo tanto c medidas b.
Del mismo modo, si c no mide b, c medidas a.
Por lo tanto c medidas uno u otro de los dos números a, b.
Q.E.D.

Contenido relacionado

Más resultados...