Teoremas de divisibilidad y algoritmo de Euclides para calcular el MCD

Teoremas de Divisibilidad

Teorema 1

Si un número natural n divide a otros dos números naturales, entonces divide a su suma y a su resta.

Demostración:

Si b divide a a y c, entonces existen enteros q y r tales que:

• a = bq + 0 → a = bq
• c = bq + 0 → c = bq

Sumando ambas ecuaciones, obtenemos:

a + c = bq + bq

a + c = b(q + q)

Por lo tanto, b divide a a + c. La demostración para la resta es similar.

Teorema 2

Si un número natural n divide a otro número natural, entonces divide a todos sus múltiplos.

Demostración:

Si b divide a a, entonces existe un entero q tal que:

a = bq

Multiplicando ambos lados de la ecuación por un entero h, obtenemos:

ah = bqh

Por lo tanto, b divide a ah.

Teorema 3

En una división entera, los divisores comunes al divisor y al resto son también divisores del dividendo.

Demostración:

Si c divide a b y r (el resto de la división de a entre b), entonces existen enteros q y s tales que:

• b = cq
• r = cs

Sustituyendo b en la ecuación de la división entera a = bq + r, obtenemos:

a = (cq)q + cs

a = c(qq + s)

Por lo tanto, c divide a a.

Teorema 4

En una división entera, los divisores comunes al dividendo y al divisor son también divisores del resto.

Demostración:

Si c divide a a y b, entonces existen enteros p y q tales que:

• a = cp
• b = cq

Sustituyendo a y b en la ecuación de la división entera a = bq + r, obtenemos:

cp = cq * q + r

r = cp - cqq

r = c(p - qq)

Por lo tanto, c divide a r.

Algoritmo de Euclides

El Algoritmo de Euclides es un método eficiente para calcular el Máximo Común Divisor (MCD) de dos números naturales. Se basa en el Teorema 4, que establece que los divisores comunes al dividendo y al divisor son también divisores del resto.

El algoritmo funciona de la siguiente manera:

1. Se divide el número mayor entre el número menor.
2. Si el resto es cero, el MCD es el divisor de la última división.
3. Si el resto no es cero, se repiten los pasos 1 y 2 utilizando el divisor de la última división como nuevo dividendo y el resto como nuevo divisor.

El último resto no nulo en este proceso es el MCD de los dos números originales.

Ejemplo

Para encontrar el MCD de 24 y 18 utilizando el Algoritmo de Euclides, se realizan las siguientes divisiones:

• 24 ÷ 18 = 1 (resto 6)
• 18 ÷ 6 = 3 (resto 0)

Como el último resto es 0, el MCD de 24 y 18 es 6.

Definiciones

• División entera: Una división donde el resto es distinto de cero. Cumple con las siguientes condiciones:
  • b ≠ 0
  • a = bq + r
  • r < b
• Múltiplos: Los productos de multiplicar un número natural por todos y cada uno de los números naturales. Si a es múltiplo de b, entonces b es divisor de a.
• Divisores comunes: Números naturales que son divisores de dos o más números naturales simultáneamente.
• MCD (Máximo Común Divisor): El mayor divisor común a dos o más números naturales.