Algoritmo de la división

Se ha sugerido que Algoritmo de la división sea fusionado en este artículo o sección (discusión). Una vez que hayas realizado la fusión de artículos, pide la fusión de historiales aquí.

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 de números enteros puede llevarse a cabo y que el resultado, además, es único.

El teorema se puede generalizar a otros conjuntos como los polinomios o los anillos matemáticos; está a la base de numerosos resultados de la aritmética, como la aritmética modular o el algoritmo de Euclides. En álgebra abstracta, está relacionado con el dominio euclídeo.

Teorema: Algoritmo de la división

Para cualesquiera enteros D y d, llamados dividendo y divisor respectivamente, con d no nulo, existen enteros únicos c y r, llamados cociente y residuo respectivamente, tales que

$~D=dc+r$

y

$0\leq r<|d|$

en donde $|d| \$ denota al valor absoluto. El algoritmo de la división es comúnmente representado con una figura similar a

$D \,$		$d \,$
$r \,$		$c \,$

Ejemplos

$320 \,$		$21 \,$
$110 \,$		$15 \,$
$5 \,$

lo que significa que $320 = (21\times 15) + 5$, y además es claro que $0\leq 5< \mid 21 \mid$.

• $13=3\cdot4+1$

• $-18=5\cdot(-4)+2$

• $147=12\cdot12+3$

• $10^3=3\cdot333+1$

• $10^2=4\cdot25+0$

Propiedades

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.

Demostración

Considérese el conjunto $R=\{D-dx|x\in\mathbb{Z}$ y $D-dx\geq 0\}$ de residuos mayores o iguales a cero. Este conjunto es no vacío, pues siempre es posible hacer $D\geq dx$ cuando $d\neq 0$ para una buena elección de x. Vemos pues que $R\subseteq\mathbb{N}$, de modo que R tiene un mínimo, digamos r. Supóngase que r = D − dc para cierto entero c. Tenemos que, al ser d no nulo,

(1) $~r-|d|<0.$

Si fuera $r\geq|d|$, se tendría $r-|d|\geq 0$, y como r = D − dc, sería $D-dc-|d|\geq 0$, o sea

$D-d(c-d)\geq 0$

o

$D-d(c+d)\geq 0$,

pero entonces $r-|d|\in R$, lo que, en vista de (1), contradice nuestra elección de r como el menor residuo en R. Ha de ser pues r < | d | , como afirma el algoritmo de la división.

Para probar la unicidad supóngase que D = dc + r = dc' + r'. Defínase $\bar{c}=c$ si $d\geq 0$ y $\bar{c}=-c$ si d < 0. De manera similar se define $\bar{c'}$. Sin pérdida de generalidad, puede suponerse que $\bar{c}\leq\bar{c'}$. De todo esto tenemos

$D=dc+r=|d|\bar{c}+r<|d|\bar{c}+|d|=|d|(\bar{c}+1)\leq|d|\bar{c'}=dc'\leq dc'+r'$,

esto es, D < D, una contradicción, de modo que debe ser c = c', luego dc + r = dc + r', y como consecuencia r = r'. Esto completa la prueba del algoritmo de la división.

Ejemplos

El primer ejemplo es detallado - muestra las sustracciones intermediarias - y el segundo sólo muestra los restos.

Cuando a o b es negativo, lo más práctico es hacer la división con los valores positivos |a| y |b| y luego adaptar el resultado. A partir del primer ejemplo, se puede hallar las divisiones de (a) 16845 por -7, de (b) -16845 por 7 y de (c) -16845 por -7:
16845 = 7 × 2406 + 3 da:
(a): 16845 = (-7) × (-2406) + 3
-16845 = (-7) × 2406 - 3 lo que no es una división euclidiana porque el resto -3 no es positivo; hay que sumarle 7, que se resta por otra parte:
(b): -16845 = (-7) × 2407 + 4.
Cambiando un signo de lugar en la división anterior se obtiene:
(c): -16845 = 7 × (-2407) + 4

Existencia y unicidad de la división euclidiana

Existencia

Sean a y b positivos, $b \neq 0$ (los demás casos son muy parecidos). La sucesión $(nb)_{n \in \mathbb{N}}$ tiende hacia el infinito, por lo tanto dobla a a partir de cierto rango. Sea q el último valor de n tal que nb sea inferior o igual a a. Entonces, por definición: $qb \leq a < (q+1)b$. Al sustraer qb a todos los miembros, obtenemos: $0 \leq a - qb < b$. Llamemos r = a − qb; entonces a = qb + r; y la desigualdad anterior se escribe $0 \leq r < b$.

Unicidad

Supongamos la existencia de dos escrituras de a: a = bq + r = bq' + r'. Por sustracción: b(q − q') = r' − r. Esto implica que b divide r' − r. Pero r y r' pertenecen al intervalo [0,b] y luego la diferencia pertenece a [ − b,b]. El único elemento de este intervalo divisible por b es cero, por lo tanto r' − r = 0, es decir r = r'. Luego bq + r = bq' + r, lo que se simplifica en q = q'.

Una calculadora facilita la división, si b > 0: $q = \left \lfloor \frac {a} {b} \right \rfloor$ y r = a − bq, donde $\lfloor \rfloor$ es la función de parte entera. Esto se obtiene dividiendo la igualdad a = bq + r por b: $\frac{a}{b} = q + \frac{r}{b}$, y como $0 \leq r < b$, la fracción $\frac{r}{b}$ pertenece a [0,1], y es por lo tanto la parte fraccionaria de $\frac{a}{b}$, y q es su parte entera.

División de polinomios

División usual

La división euclidiana se generaliza a todos los anillos graduados, es decir en los anillos donde existe una función llamada grado, con valor en {- ∞} ∪ N, notada d ^o, que verifique (entre otras cosas) 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(Xⁿ) = 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).

La división euclidiana de polinomios permite encontrar el máximo común divisor gracias al algoritmo de Euclides.

Sin embargo, su uso más común es para hallar las raíces de un polinomio dado. En tal caso, el resto tiene que ser nulo, y la división euclidiana es una división en el sentido usual: A = B·Q equivale a Q = A/B, que permite factorizar con rapidez. La resolución de una ecuación de tercer grado requiere mucho tiempo si se aplica el método general. Lo mejor es tratar de encontrar una raíz evidente α y luego dividir P por X - α.

Ejemplo: Sea P = 63X³ - 86X² + 3X + 20 un polinomio de grado 3, y se quiere hallar todas sus raíces. Miremos primero si 0, 1 o -1 es raíz evidente. Por suerte (...) P(1) = 63 - 86 + 3 + 20 = 0. Como x_o = 1 es raíz, podemos factorizar por X - 1, lo que hacemos mediante una división euclidiana:

El resto es nulo, lo que confirma que 1 es raíz, y tenemos: P = (X-1)·Q, con Q = 63X² - 23X - 20. Luego, las raíces de Q se obtienen resolviendo la ecuación de segundo grado Q(x) = 0 y se obtiene $x_2 = - \frac {4} {9} \ \ y \ \ x_3 = \frac {5} {7}$ y por último se puede completar (y arreglar) la factorización de P: P = (X-1)(7X - 5)(9X + 4).

Si A es un anillo, la división euclidiana en A[X] no es siempre posible. Por ejemplo, en Z[X], los polinomios con coeficientes enteros, no es posible dividir X² por 2X + 3, porque el cociente (trabajando en R[X]) es: X/2, y no pertenece a Z[X].

La única condición para que sea posible es que coeficiente dominante (el del monomio de mayor grado) sea inversible. En el ejemplo detallado, la división por X - 1 ( = 1X - 1) no causó problema alguno porque el coeficiente dominante es 1, inversible en Z.

División según las potencias crecientes

En algunos casos es interesante considerar que X es pequeño frente a 1 y hacer las divisiones al revés, empezando por las constantes (que son los términos mayores) y terminando por los Xⁿ, con n grande. Formalmente, se modifica la definición del grado: d ^o (Xⁿ) = - n. La diferencia es que ya no hay unicidad, y es necesario fijarse por antelación una precisión, es decir un grado máximo al resto.

Por ejemplo, dividamos 1 por 1 - X al orden 3: el resto deber haber como término más fuerte (aquí el monomio de menor exponente) a lo mejor X⁴. La igualdad obtenida (en azul) equivale a:

$\frac {1 - X^4} {1 - X} = 1+ X + X^2 + X^3$

lo que, además de ser cierta, es un caso especial de la suma de términos de una sucesión geométrica:

$1+q+q^2 + ... + q^n = \frac {1-q^{n+1}} {1-q}$

y cada valor de n corresponde a una división euclidiana con una precisión distinta.

Otro punto de vista es considerar a $1 + X + X^2 + ... + X^n \$ como el inicio del desarrollo de $\frac {1} {1-X}$ en serie de Taylor.

Más generalmente, la serie de Taylor de una función racional se obtiene mediante la división euclidiana de la serie de Taylor del numerador por la del denominador. Por ejemplo, consideremos la función trigonométrica tangente: $\tan = \frac {\sin} {\cos}$, y busquemos su desarrollo alrededor de 0 al orden 5. Hay que conocer las series al orden 5 (por lo menos) del seno y del coseno, y dividirlas descartando sistemáticamente los términos de orden mayor que aparecen en el cálculo. Como la función tangente es par, sólo hay tres monomios (en X, X³ y X⁵) que buscar. El resultado es $\tan x = x + \frac {x^3} {3} + \frac {2x^5} {15} + O(x^{7})$

La división euclidiana también existe en los anillos de polinomios de múltiples variable K[X,Y,Z...], donde hay varias maneras de definir el grado (parcial, total...) y otras tantas de proceder a la división.

Véase también

• Dominio euclídeo
• Norma euclídea
• Valor absoluto
• Anillo de polinomios
• Teoría de números
• División euclidiana

Referencias

El contenido de este artículo incorpora material de una entrada de la Enciclopedia Libre Universal, publicada en español bajo la licencia Creative Commons Compartir-Igual 3.0.