El algoritmo de división de Euclides es una técnica para calcular el factor común más alto (HCF) de dos enteros positivos dados. HCF de dos enteros positivos a y b es el entero positivo más grande d que divide tanto a a como a b. Para comprender el Algoritmo de la División de Euclides, primero debemos comprender el Lema de la División de Euclides .
Lema de la división de Euclides
El Lema de la División de Euclides da la relación entre todos los componentes de la División. Veamos el enunciado del Lema de la División de Euclides:
Para cualquier 2 entero positivo a y b existe un único entero q y r,
Tal que: a = bx (q + r),
donde 0 <= r < segundo
Entendamos visualmente el lema de la división de Euclides . En el siguiente diagrama, el Dividendo 27 es a y el Divisor 8 es b.
El Cociente 3 es q y el Resto 3 es r
Como se puede ver en la siguiente imagen:
Así, el lema de división: a = bx (q + r) se puede escribir como:
Dividendo = (Divisor x Cociente) + Resto
- El lema de división de Euclides tiene muchas aplicaciones relacionadas con la divisibilidad de enteros
- Se puede usar para encontrar el HCF de dos números.
- HCF significa Máximo Común Divisor.
Usando el lema de división para encontrar el HCF de dos números
El proceso de encontrar el HCF de dos números usando el LEMA DE LA DIVISIÓN DE EUCLID se llama “ALGORITMO DE LA DIVISIÓN DE EUCLID”.
Ejemplo 1: ¿Vamos a encontrar el HCF de 135 y 255?
Solución:
Paso 1: Aplica el Lema de la División al 255 y al 135, dividiendo 255 por 135.
Paso 2: Ahora, el Resto se convierte en el divisor y el divisor anterior se convierte en el dividendo
Paso 3: Nuevamente se aplica el lema de división a este nuevo par de dividendos y divisores
Paso 4: Ahora 15 es nuestro nuevo Divisor y 120 es el nuevo Dividendo.
El Divisor que hace el Remanente Cero es el HCF de Dos Números.
Entonces 15 es el HCF de 255 y 135.
Ejemplo 2: ¿Usar el algoritmo de división de Euclides para encontrar el HCF de 867 y 255?
Solución:
Paso 1: Como 867 > 255, aplicamos el lema de división a 867 y 255, para obtener
867 = 255 x 3 + 102
Paso 2: Como el Resto 102 ≠ 0, aplicamos el lema de división a 867 y 255, para obtener
255 = 102 x 2 + 51
Paso 3: Consideramos el nuevo divisor 102 y el nuevo Resto 51 y aplicamos el lema de división para obtener
102 = 51×2 + 0
El resto ahora se ha convertido en cero, por lo que nuestro procedimiento se detiene. Dado que el divisor en esta etapa es 51, el HCF de 255 y 867 es 51.
Ejemplo 3: ¿Usar el algoritmo de división de Euclides para encontrar el HCF de 4052 y 12576?
Solución:
Paso 1: Como 12576 > 4052, aplicamos el Lema de división a 867 y 255, para obtener
12576 = 4052 x 3 + 420
Paso 2: Dado que el Resto 420 ≠ 0, aplicamos el lema de división a 12576 y 4052, para obtener
4052 = 420 x 9 + 272
Paso 3 : Consideramos el nuevo divisor 420 y el nuevo Resto 272 y aplicamos el lema de división para obtener
420 = 272×1 + 148
Consideramos el nuevo divisor 272 y el nuevo Resto 148 y aplicamos el lema de división para obtener
272 = 148×1 + 124
Consideramos el nuevo divisor 148 y el nuevo Resto 124 y aplicamos el lema de división para obtener
148 = 124×1 + 24
Consideramos el nuevo divisor 124 y el nuevo Resto 24 y aplicamos el lema de división para obtener
124 = 24×5 + 4
Consideramos el nuevo divisor 24 y el nuevo Resto 4 y aplicamos el lema de división para obtener
24 = 4×6 + 0
El resto ahora se ha convertido en cero, por lo que nuestro procedimiento se detiene. Dado que el divisor en esta etapa es 4, el HCF de 4052 y 12576 es 4.