División euclídea

De Wikipedia, la enciclopedia libre
(Redirigido desde «Algoritmo de la división»)
Saltar a: navegación, búsqueda

En matemáticas, y más precisamente en la aritmética, la división euclidiana (o euclídea), también llamada algoritmo de la división, es un teorema que asegura que «el proceso habitual de división entre números enteros» puede llevarse a cabo y que el resultado, además, es único.

Un «algoritmo de división entera» es cualquier método efectivo que produce un cociente y un residuo. Existen numerosos métodos para efectuar estos cálculos, como por ejemplo la división larga, la factorización de enteros o la aritmética modular. El algoritmo de la división euclídea (para números enteros) se encuentra a la base de numerosos resultados de la aritmética (como por ejemplo el algoritmo de Euclides para calcular el máximo común divisor de dos enteros) y la teoría de números; en álgebra abstracta, está relacionado con el dominio euclídeo.

División euclídea de números naturales[editar]

Dados dos números naturales, el dividendo, m, y el divisor, d, que debe ser mayor que cero, llamamos cociente, q al mayor de los números que multiplicado por el divisor es menor o igual que el dividendo.

 q \; = \; \max \ \{ \ x \in N \;| \; x  d \le m \ \}

Llamamos resto, r, a la diferencia entre el dividendo y el producto del cociente y el divisor.

 r \; = \; m - q d

El resto verifica la inecuación  0 \le r < d .

De la ecuación anterior, se deduce inmediatamente la siguiente:

 m \; = \; q d + r


Ejemplos[editar]

 320 \,

 21 \,

 110 \,  15 \,
 5 \,

lo que significa que 320 = (21\times 15) + 5, con 0\leq 5< \mid 21 \mid.

Teorema: Algoritmo de la división[editar]

División euclídea en los números naturales[editar]

Dados dos números naturales a y b, con b distinto de 0, la división euclídea asocia un cociente q y un resto r, ambos números naturales, que verifican:

  • a = b\ q+r\,
  • r < b\;

La pareja (q, r) es única.

De manera formal:

\forall (a,b)\in\mathbb{N}\times\mathbb{N}^*, \exists! (q, r) \in\mathbb{N}^2 / a=b\ q+r \quad \text{con} \quad r< b
Teorema de la división euclídea para los números naturales
Sean a y b dos enteros positivos, con b no nulo.
Existencia

Considérese el conjunto E definido por:

E = \left\{ x \in \mathbb{N}\quad | \quad \exist z \in \mathbb{N}\, x = a - bz\right\}

E es no vacío pues contiene a. Como E es una parte no vacía de N, por axioma, el mínimo de E existe. Nótese r ese mínimo y q el entero que lo define, es decir, aquel que verifique la igualdad a - b*q = r. Por construction, r es un número natural. El entero r - b no puede ser elemento de E por lo que es estrictamente negativo, de modo que r debe ser estrictamente menor que b. Esto demuestra la existencia.

Unicidad

Supóngase que existen cuatro enteros q1,q2, r1 y r2 que forman dos parejas de soluciones. Por diferencia, (q1 - q2)*b + (r1 - r2) es cero.

Esta igualdad muestra que b divide a r1 - r2 . Como r1 y r2 son estrictamente menores que b y positivos, r1 - r2 está comprendido estrictamente entre - b y b, por lo que el único valor posible múltiplo de b para r1 - r2 es cero. En conclusión, r1 es igual a r2 por lo que q1 también es igual a q2.

División euclídea en los números enteros[editar]

llamado también algoritmo de la división para los número enteros

Dados dos números enteros a y b, con b no nulo. Entonces existen dos únicos enteros q y r

  • 0 ≤ r < |b|, tales que
  • a = b.q+r\, [1]
  • A q se denomina cociente y a r, resto de la división que siempre es un entero no negativo.[2] [3]

Referencia[editar]

  1. Albert: "Álgebra superior" ISBN 968-18-4041-0 pág. 45
  2. Hefez: "Curso de álgebra" vol. 1 ISBN 9972-9394-1-3 pp57, 58, 59
  3. Ayres Jr.: "Teoría y problemas de álgebra moderna", Libros Mc Graw Hill, pág. 50

De manera formal:

\forall (a,b)\in\mathbb{Z}\times\mathbb{Z}^*, \exists q, r\in\mathbb{Z} | a=b.q+r \quad \text{con} \quad |r| < |b|
Teorema de la división euclídea para los números enteros
La definición de la división euclídea sobre los números naturales permite probar la existencia de q1 et r1 tales que
|a| = |b|q_1 + r_1 con r _1< |b|

Un estudio por inspección sobre los signos respectivos de a y b permite establecer la existencia de al menos un cociente y un resto por la división euclídea de a por b:

para a y b negativos, cociente q1 y resto - r1;
para a negativo y b positivo, cociente - q1 y resto - r1;
para a positivo y b negativo, cociente - q1 y resto r1;
para a y b positivos, cociente q1 y resto r1.

La unicidad no está siempre garantizada sin la condición r positivo o nulo.

En efecto, si a = bq + r y r es estrictamente positivo, entonces a = b(q+1) + r - b en donde |r-b| < |b| es otra pareja de soluciones.

Propiedades[editar]

Por el algoritmo de la división se deduce que \mathbb{Z} es un dominio euclídeo tomando como norma el valor absoluto. Una consecuencia inmediata del algoritmo de la división es que puede usarse el algoritmo de Euclides para calcular el máximo común divisor de dos números enteros.

Un concepto que generaliza el algoritmo de la división es el de norma euclídea. De este modo cualquier dominio euclídeo cumple con un principio similar al algoritmo de la división, como es el caso, por ejemplo, de un anillo de polinomios \mathbb{K}[x] en que \mathbb{K} es un cuerpo.

División de polinomios[editar]

La división euclidiana se generaliza a todos los anillos graduados, es decir en los anillos donde existe una función llamada grado que verifique: d o(P·Q) = d o(P) + d o(Q).

Los ejemplos más usuales lo constituyen los anillos de polinomios K[X], donde K es un cuerpo, como R o C, y donde d o(Xn) = n y d o(0) = - ∞. En este contexto, se remplaza la condición 0≤ r < b que a priori no tiene sentido porque el anillo ya no es totalmente ordenado, por d o (R) < d o(B), y claro, se mantiene A = B·Q + R (para los polinomios, la costumbre es utilizar las mayúsculas).

Si los polinomios tienen por coeficientes elementos de un cuerpo K, es posible definir una división euclídea sobre los polinomios (llamada división) según el orden decreciente de las potencias.

A dos polinomios A y B, la división euclídea asocia un único cociente Q y un único resto R, ambos polinomios, tales que:

  • A=B\cdot Q+R\,
  • \operatorname{grad}(R) < \operatorname{grad}(B)

Formalmente:

\forall (A,B)\in\mathbb{K}[X]\times\mathbb{K}[X]^*,\quad \exists !Q, R\in\mathbb{K}[X], A=B\cdot Q+R \quad \mathrm{con} \quad \operatorname{grad}(R) < \operatorname{grad}(B)

La unicidad está garantizada, pero es necesario que K sea un cuerpo para que la existencia lo sea también.

Véase también[editar]

Bibliografía[editar]