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.

Contenido

1 Teorema: Algoritmo de la división
2 Ejemplos
3 Propiedades
4 Demostración
5 Ejemplos
6 Existencia y unicidad de la división euclidiana
- 6.1 Existencia
- 6.2 Unicidad
7 División de polinomios
- 7.1 División usual
- 7.2 División según las potencias crecientes
8 Véase también
9 Referencias

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$

$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 - d c$ 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 - d c$ , sería $D-dc-|d|\geq 0$ , o sea

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

$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 = d c + r = d c' + 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 $d c + r = d c + 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 $n b$ sea inferior o igual a $a$ . Entonces, por definición: $qb \leq a < (q+1)b$ . Al sustraer $q b$ a todos los miembros, obtenemos: $0 \leq a - qb < b$ . Llamemos $r = a - q b$ ; entonces $a = q b + r$ ; y la desigualdad anterior se escribe $0 \leq r < b$ .

Unicidad

Supongamos la existencia de dos escrituras de $a$ : $a = b q + r = b q' + 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 $b q + r = b q' + 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 - b q$ , donde $\lfloor \rfloor$ es la función de parte entera. Esto se obtiene dividiendo la igualdad $a = b q + 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.

División euclidiana creciente polinomio.png

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

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.

Categorías:

Teoría de números elemental
Aritmética elemental

Wikimedia foundation. 2010.

Игры ⚽ Поможем сделать НИР

Mira otros diccionarios:

Algoritmo de Euclides — El algoritmo de Euclides es un método antiguo y eficaz para calcular el máximo común divisor (MCD). Fue originalmente descrito por Euclides en su obra Elementos. El algoritmo de Euclides extendido es una ligera modificación que permite además… … Wikipedia Español
División (matemática) — En matemática, la división es una operación aritmética de descomposición que consiste en averiguar cuántas veces un número (divisor) está contenido en otro número (dividendo). La división es la operación inversa de la multiplicación. Según su… … Wikipedia Español
Algoritmo — Los diagramas de flujo sirven para representar algoritmos de manera gráfica. En matemáticas, ciencias de la computación y disciplinas relacionadas, un algoritmo (del griego y latín, dixit algorithmus y éste a su vez del matemático persa Al… … Wikipedia Español
Algoritmo bisiesto — Saltar a navegación, búsqueda Un año es bisiesto si es divisible entre 4, excepto aquellos divisibles entre 100 pero no entre 400. En programación, el algoritmo para calcular si un año es bisiesto es un algoritmo útil para la realización de… … Wikipedia Español
División por tentativa — Saltar a navegación, búsqueda La división por tentativa es el algoritmo de factorización de enteros más sencillo y fácil de entender. Dado un entero compuesto n (a lo largo de este artículo, n será el entero a factorizar ), la división por… … Wikipedia Español
Algoritmo de de Casteljau — Saltar a navegación, búsqueda El algoritmo de de Casteljau es, en el campo del análisis numérico de la matemática, un método recursivo para calcular polinomios en la forma de Bernstein o base de Bernstein o en las curvas Bézier, toma su nombre de … Wikipedia Español
División polinomial — Saltar a navegación, búsqueda En álgebra, división polinomial es un algoritmo que permite dividir un polinomio por otro polinomio de igual o menor grado. El algoritmo es una versión generalizada de la técnica aritmética de división. Es fácilmente … Wikipedia Español
División euclídea — Saltar a navegación, búsqueda La división euclidiana (o euclídea) del entero a por el entero no nulo b es el cálculo que permite encontrar los enteros q y r tales que: a = bq + r, con 0 ≤ r < |b| a se llama el… … Wikipedia Español
Algoritmo divide y vencerás — En la cultura popular, divide y vencerás hace referencia a un refrán que implica resolver un problema difícil, dividiéndolo en partes más simples tantas veces como sea necesario, hasta que la resolución de las partes se torna obvia. La solución… … Wikipedia Español
Algoritmo probabilista — Un algoritmo probabilista (o probabilístico) es un algoritmo que basa su resultado en la toma de algunas decisiones al azar, de tal forma que, en promedio, obtiene una buena solución al problema planteado para cualquier distribución de los datos… … Wikipedia Español

Los diccionarios y las enciclopedias sobre el Académico

Algoritmo de la división

Contenido

Teorema: Algoritmo de la división

Ejemplos

Propiedades

Demostración

Ejemplos