Divisibilidad y factorización · Definición

Lema de Euclides

teoría de números elementaldivisibilidad y factorización

Antes de empezar necesitas conocer

Este resultado extiende a productos de varios factores la idea de que un primo no puede repartirse entre dos números sin dividir a uno de ellos. Se apoya en la identidad de Bézout para demostrarse.

Definición

Si un primo \(p\) divide al producto \(ab\), entonces \(p\) divide a \(a\) o a \(b\). Es la propiedad clave que distingue a los primos de los compuestos.

\[p \mid ab \Rightarrow p \mid a \ \lor\ p \mid b\]

Si \(p\) es primo y \(p \nmid a\), entonces \(\operatorname{mcd}(p,a)=1\). Por la identidad de Bézout existen enteros \(x,y\) con \(px+ay=1\). Multiplicando por \(b\) se obtiene \(pbx+aby=b\); como \(p \mid ab\), \(p\) divide a \(aby\) y también a \(pbx\), así que \(p\) divide a \(b\). Por inducción, el resultado vale para productos de cualquier cantidad de factores.

Tomemos \(p=5\), \(a=12\), \(b=15\). Como \(5 \mid 180\) con \(180=12\cdot 15\), y \(5\nmid 12\), debe ocurrir que \(5 \mid 15\), lo cual es cierto. Así el lema se verifica en un caso concreto antes de generalizarlo.

Un error frecuente es aplicar el lema a un número compuesto, por ejemplo afirmar que \(6 \mid ab\) implica \(6 \mid a\) o \(6 \mid b\). Con \(a=2\), \(b=3\) se tiene \(6 \mid 6\) pero \(6 \nmid 2\) y \(6 \nmid 3\). La hipótesis de primalidad es indispensable.

Para pensar

¿Por qué p debe ser primo para que el lema valga?

Porque si p es compuesto falla: \(6\) divide a \(2\cdot 3\) sin dividir a \(2\) ni a \(3\).

Ejercicios 10

  1. Si \(p\) es primo y \(p \mid ab\), ¿qué puedes concluir?
  2. ¿El lema de Euclides exige que \(p\) sea primo?
  3. ¿Cuál es el enunciado correcto del lema de Euclides?
  4. Si \(p\) es primo y \(p \mid 35\), ¿qué valor puede tener \(p\)?
  5. ¿Cuál de estas afirmaciones sobre un primo \(p\) que no divide a \(a\) es verdadera?
  6. Si \(7 \mid 12x\), ¿qué puedes concluir sobre \(x\)?
  7. Si \(11 \mid ab\) y \(11 \nmid a\), ¿qué ocurre con \(b\)?
  8. Si \(p\) es primo y \(p \mid a^2\), ¿qué se concluye?
  9. Si \(p\) es primo y \(p \mid abc\) con \(p \nmid a\) y \(p \nmid b\), ¿qué se concluye?
  10. Si \(p\) es primo, \(p \mid ab\) y \(p \mid a+b\), ¿qué se concluye?

Referencias

  • David M. Burton, Elementary Number Theory, 7th edition, McGraw-Hill, 2011. cap. 2 y 3
  • Ivan Niven, Herbert S. Zuckerman, Hugh L. Montgomery, An Introduction to the Theory of Numbers, 5th edition, Wiley, 1991. cap. 1