5.2: algoritmo de división

Última actualización
Guardar como PDF

Page ID: 112902

\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

Cuando dividimos un entero positivo (el dividendo) por otro entero positivo (el divisor), obtenemos un cociente. Multiplicamos el cociente al divisor, y restamos el producto del dividendo para obtener el resto. Tal división produce dos resultados: un cociente y un resto.

Así es como normalmente dividimos 23 por 4:

\ [\ require {encerrar}
\ begin {array} {rll}
5 &&\\ [-3pt]
4\ encerrar {longdiv} {23}\ kern-.2ex\\ [-3pt]
\ subrayado {\ phantom {0} 20} &&\\ [-3pt]
\ phantom {00} 3
\ end {array}\ nonumber\]

En general, la división\(b\div a\) toma la forma

\ [\ require {encerrar}
\ begin {array} {rll}
q &&\\ [-3pt]
a\ encerrar {longdiv} {\ phantom {0} b}\ kern-.2ex\\ [-3pt]
\ subrayado {\ phantom {0} aq} &&\ [-3pt]
\ phantom {00} r
\ end {array}\ nonumber\]

de manera que\(r=b-aq\), o equivalentemente,\(b=aq+r\). Por supuesto, ambos\(q\) y\(r\) son enteros. Sin embargo, las siguientes “divisiones”

\ [{\ require {encerrar}\ begin {array} {rll}
4 &&\\ [-3pt]
4\ encerrar {longdiv} {23}\ kern-.2ex\\ [-3pt]
\ subrayado {\ phantom {0} 16} &&\\ [-3pt]
\ phantom {00} 7
\ end {array}} {\ require {encerrar}
\ begin {array} rll}
2 &&\\ [-3pt]
4\ encierra {longdiv} {23}\ kern-.2ex\\ [-3pt]
\ subrayado {\ phantom {0} 8} &&\\ [-3pt]
\ phantom {00} 15
\ end {array}} {\ require {encerrar}
\ begin {array} {rll}
6 &&\\\ [-3pt]
4\ encierra {longdiv} {23}\ kern-.2ex\\ [-3pt]
\ subrayado {\ phantom {0} 24} &&\\ [-3pt]
\ phantom {00} -1
\ end {array}} {\ require {encerrar}
\ begin {array} {rll}
7 &&\\ [-3pt]
4\ encerrar {longdiv} {23}\ kern-.2ex\\ [-3pt]
\ subrayado {\ phantom {0} 28} &&\\ [-3pt]
\ phantom {00} -5
\ end {array}}\ nonumber\]

también satisfacen el requisito\(b=aq+r\), pero eso no es lo que normalmente hacemos. Esto significa tener\(b=aq+r\) solo no es suficiente para definir qué cociente y resto son. Necesitamos una definición más rígida.

Teorema\(\PageIndex{1}\label{thm:divalgo}\)

Dados los enteros\(a\) y\(b\), donde\(a>0\), existen enteros\(q\) y\(r\) tal que\[b = aq + r, \nonumber\] donde\(0\leq r< a\). además,\(q\) y\(r\) están determinados de manera única por\(a\) y\(b\).

Los enteros\(b\),\(a\),\(q\), y\(r\) se denominan dividendo, divisor, cociente y resto, respectivamente. Observe que\(b\) es un múltiplo de\(a\) si y solo si\(r=0\).

El algoritmo de división describe lo que sucede en la división larga. Estrictamente hablando, no es un algoritmo. Un algoritmo describe un procedimiento para resolver un problema. El teorema no nos dice cómo encontrar el cociente y el resto. Algunos matemáticos prefieren llamarlo el teorema de la división. Aquí, seguimos la tradición y la llamamos el algoritmo de división.

Comentario

Este es el esquema de la prueba:

Describir cómo encontrar los enteros\(q\) y\(r\) tal que\(b=aq+r\).
Demuestre que nuestra elección de\(r\) satisface\(0\leq r< a\).
Establecer la singularidad de\(q\) y\(r\).

En cuanto a la última parte de la prueba: para demostrar que un cierto número\(x\) está determinado de manera única, un enfoque típico\(x'\) es asumir que es otra opción que satisface la condición dada, y demostrar que debemos tener\(x=x'\).

Prueba

Primero mostramos la existencia de\(q\) y\(r\). Let\[S = \{ b-ax \mid x\in\mathbb{Z} \mbox{ and } b-ax\geq 0 \}. \nonumber\] Claramente,\(S\) es un conjunto de enteros no negativos. Para poder aplicar el principio del orden correcto, necesitamos demostrar que no\(S\) está vacío. Aquí hay una prueba constructiva.

Caso 1. Si\(b\geq 0\), podemos establecer\(x=0\). Entonces\(b-ax=b\geq0\).
Caso 2. Si\(b < 0\), establecer\(x=b\).
Ya que\(a\geq1\), tenemos\(1-a\leq0\). Entonces\[b-ax = b-ab = b(1-a) \geq 0. \nonumber\]

Dado que no\(S\) está vacío, se desprende del principio de ordenamiento correcto que\(S\) tiene un elemento más pequeño. Llámenlo\(r\). De la definición de\(S\), existe algún entero\(q\) tal que\(b − aq = r\).

Paso 2: Demostrar que r satisface el criterio\(0 \leq r < a\).

Entonces\(t \in S\). Ahora\(t = r − a < r\) sugiere que hemos encontrado otro elemento en el\(S\) que es incluso más pequeño que\(r\). Esto contradice la minimalidad de\(r\). Por lo tanto\(r < a\).

Por último, tenemos que establecer la singularidad de ambos\(q\) y\(r\). Dejar\(q'\) y\(r'\) ser enteros tales que\[b=aq'+r', \qquad 0\leq r'< a. \nonumber\] De\(aq+r = b = aq'+r'\), nos encontremos\(a(q-q') = r'-r\). De ahí\[a\,|q-q'| = |r'-r|. \nonumber\] que Since\(|r'-r|\) sea un entero\(|r'-r|\neq0\), si, tendríamos\(a\leq |r'-r|\). De\(0\leq r,r'<a\), deducimos eso\(|r'-r|<a\), lo que contradice claramente nuestra observación de que\(a\leq|r'-r|\). De ahí,\(|r'-r|=0\). Entonces\(r'=r\). De ello se deduce que\(q'=q\). Entonces el cociente\(q\) y el resto\(r\) son únicos.

A continuación, lo demostramos\(0\leq r<a\). La definición de nos\(S\) dice inmediatamente eso\(r\geq0\), así que solo necesitamos demostrarlo\(r<a\). Supongamos, por el contrario,\(r\geq a\). Entonces\(r = a+t\) para algún entero\(t\geq 0\). Ahora\(b-aq = r = a + t\) implica que\[0 \leq t = b-aq-a = b-a(q+1). \nonumber\] So\(t\in S\). Ahora\(t = r-a < r\) sugiere que hemos encontrado otro elemento en el\(S\) que es incluso más pequeño que\(r\). Esto contradice la minimalidad de\(r\). Por lo tanto\(r < a\).

No deberías tener ningún problema para dividir un entero positivo por otro entero positivo. Este es el tipo de división larga que normalmente realizamos. Es más desafiante dividir un entero negativo por un entero positivo. Cuando\(b\) es negativo, el cociente también\(q\) será negativo, pero el resto\(r\) debe ser no negativo. En cierto modo,\(r\) es el factor decisivo: elegimos de\(q\) tal manera que el resto\(r\) satisfaga la condición\(0\leq r<a\).

En general, para cualquier entero\(b\), dividir\(b\) por\(a\) produce un número decimal. Si el resultado no es un número entero, redondearlo al siguiente entero más pequeño (ver Ejemplo 6.1.3). Es el cociente\(q\) que queremos, y el resto\(r\) se obtiene de la resta\(r=b-aq\). Por ejemplo,\[\frac{-22}{\;\;7} = -3.1428\ldots\,. \nonumber\] Redondearlo hacia abajo produce el cociente\(q=-4\), y el resto lo es\(r=-22-7(-4)=6\); y nosotros sí tenemos\(-22=7\cdot(-4)+6\).

Ejercicio práctico\(\PageIndex{1}\label{he:divalgo-01}\)

Calcular los cocientes\(q\) y los restos\(r\) cuando\(b\) se divide por\(a\):

\(b= 128\),\(a=7\)
\(b=-128\),\(a=7\)
\(b=-389\),\(a=16\)

Asegúrese de verificar eso\(b=aq+r\).

El algoritmo de división puede generalizarse a cualquier entero distinto de cero\(a\).

Corolario\(\PageIndex{2}\label{cor:divalgo}\)

Dado cualquier número entero\(a\) y\(b\) con\(a\neq 0\), existen números enteros determinados de manera única\(q\) y\(r\) tal que\(b = aq +r\), donde\(0\leq r < |a|\).

Prueba: Sólo tenemos que considerar el caso de\(a<0\). Ya que\(-a>0\), el Algoritmo Euclideano original asegura que existen números enteros determinados de manera única\(q'\) y\(r\) tal que\[b = (-a)\cdot q' + r, \nonumber\] donde\(0\leq r<-a=|a|\). Por lo tanto, podemos establecer\(q=-q'\).

ejemplo\(\PageIndex{1}\label{eg:divalgo-01}\)

No todas las calculadoras o programas informáticos computan\(q\) y\(r\) la forma en que queremos que se hagan en matemáticas. La solución más segura es computar de la\(|b| \div |a|\) manera habitual, inspeccionar el resto para ver si se ajusta al criterio\(0\leq r<|a|\). Si es necesario, ajustar el valor de\(q\) para que el resto\(r\) satisfaga el requisito\(0\leq r<|a|\). Aquí hay algunos ejemplos:\[\begin{array}{|r|r|r@{\;=\;}l|r|r|} \hline b & a & b & aq+r & q & r \\ \hline 14 & 4 & 14 & 4\cdot3+2 & 3 & 2 \\ -14 & 4 & -14 & 4\cdot(-4)+2 & -4 & 2 \\ -17 & -3 & -17 & (-3)\cdot6+1 & 6 & 1 \\ 17 & -3 & 17 & (-3)\cdot(-5)+2 & -5 & 2 \\ \hline \end{array} \nonumber\]

El cociente\(q\) puede ser positivo o negativo, y el resto\(r\) es siempre no negativo.

Definición

Dados enteros\(a\) y\(b\), con\(a\neq 0\), let\(q\) y\(r\) denotan los enteros únicos tal que\(b=aq+r\), donde\(0\leq r<|a|\). Defina los operadores binarios\(\mathrm{ div }\) y de\(\bmod\) la siguiente manera:

Por lo tanto,\(b ~ \mathrm{ div } ~ a\) da el cociente, y\(b\bmod a\) produce el resto de la división entera\(b\div a\). Recordemos que\(b ~ \mathrm{ div } ~ a\) puede ser positivo, negativo, o incluso cero. Pero siempre\(b\bmod a\) es un entero no negativo menor que\(|a|\).

ejemplo\(\PageIndex{2}\label{eg:divalgo-02}\)

Del último ejemplo, tenemos

\(14 ~ \mathrm{ div } ~ 4 = 3\), y\(14\bmod 4 = 2\).
\(-14 ~ \mathrm{ div } ~ 4 =-4\), y\(-14\bmod 4 = 2\).
\(-17 ~ \mathrm{ div } ~ -3 = 6\), y\(-17\bmod-3 = 1\).
\(17 ~ \mathrm{ div } ~ -3 =-5\), y\(17\bmod-3 = 2\).

No olvides revisar los cómputos, y recuerda que no\(a\) es necesario que sean positivos.

Ejercicio práctico\(\PageIndex{2}\label{he:divalgo-02}\)

Complete la siguiente tabla:

\[\begin{array}{|r|r|r|r|} \hline b & a & b ~ \mathrm{ div } ~ a & b\bmod a \\ \hline 334 & 15 & \qquad\qquad & \qquad\qquad \\ 334 & -15 & & \\ -334 & 15 & & \\ -334 & -15 & & \\ \hline \end{array} \nonumber\]No lo olvides: siempre\(b\bmod a\) es no negativo.

ejemplo\(\PageIndex{3}\label{eg:divalgo-03}\)

Dejar\(n\) ser un entero tal que\[n ~ \mathrm{ div } ~ 6 = q, \qquad \mbox{and} \qquad n\bmod6 = 4. \nonumber\] Determine los valores de\((2n+5) ~ \mathrm{ div } ~ 6\), y\((2n+5)\bmod6\).

Solución: La información dada implica que\(n=6q+4\). Entonces\[2n+5 = 2(6q+4)+5 = 12q+13 = 6(2q+2)+1. \nonumber\] Por lo tanto\((2n+5) ~ \mathrm{ div } ~ 6 = 2q+2\),, y\((2n+5)\bmod6 = 1\).

Ejercicio práctico\(\PageIndex{3}\label{he:divalgo-03}\)

Dejar\(n\) ser un entero tal que\[n ~ \mathrm{ div } ~ 11 = q, \qquad\mbox{and}\qquad n\bmod11 = 5. \nonumber\] Calcular los valores de\((6n-4) ~ \mathrm{ div } ~ 11\) y\((6n-4)\bmod11\).

ejemplo\(\PageIndex{4}\label{eg:divalgo-04}\)

Supongamos que hoy es miércoles. ¿Qué día de la semana es dentro de un año?

Solución: Denotar domingo, lunes,..., sábado como Día 0, 1,... 6, respectivamente. Hoy es el Día 3. Un año (suponiendo 365 días en un año) a partir de hoy será el Día 368. Ya\[368 = 7\cdot52+4, \nonumber\] que será el Día 4 de la semana. Por lo tanto, un año a partir de hoy será el jueves.

Ejercicio práctico\(\PageIndex{4}\label{he:divalgo-04}\)

Supongamos que hoy es viernes. ¿Qué día de la semana son 1000 días a partir de hoy?

Cualquier entero dividido por 7 producirá un resto entre 0 y 6, inclusive. \[A_i = \{ x\in\mathbb{Z} \mid x\bmod 7 = i \} \quad\mbox{ for } 0\leq i\leq 6, \nonumber\]Definimos encontramos\[\mathbb{Z} = A_0\cup A_1\cup A_2\cup A_3\cup A_4\cup A_5\cup A_6, \nonumber\] donde los conjuntos\(A_i\) son disjuntos por pares. La colección de conjuntos\[\{A_0,A_1,A_2,A_3,A_4,A_5,A_6\} \nonumber\] se llama partición de\(\mathbb{Z}\), porque cada entero pertenece a uno y sólo a uno de estos siete subconjuntos. También decimos que\(\mathbb{Z}\) es una unión disjunta de\(A_0,A_1,\ldots,A_6\). El mismo argumento también se aplica a la división por cualquier entero\(n\geq2\).

En general, una colección o familia de conjuntos finitos\(\{S_1,S_2,\ldots, S_n\}\) se denomina partición del conjunto\(S\) si\(S\) es la unión disjunta de\(S_1,S_2,\ldots\,S_n\). La partición es un concepto muy importante, porque divide los elementos de\(S\) en\(n\) clases de\(S_1,S_2,\ldots,S_n\) tal manera que cada elemento de\(S\) pertenece a una clase única. Volveremos a revisar la partición cuando estudiemos las relaciones en el Capítulo 7.

Resumen y revisión

La división de enteros se puede extender a enteros negativos.
Dado cualquier entero\(b\), y cualquier entero distinto de cero\(a\), existen números enteros determinados de forma única\(q\) y\(r\) tal que\(b=aq+r\), donde\(0\leq r<|a|\).
Llamamos\(q\) al cociente, y\(r\) al resto.
La razón por la que tenemos opciones únicas\(q\) y\(r\) es el criterio en el que nos colocamos\(r\). Tiene que satisfacer el requisito\(0\leq r<|a|\).
De hecho, el criterio\(0\leq r<|a|\) es el factor decisivo más importante en nuestra elección de\(q\) y\(r\).
Definimos dos operaciones binarias en enteros. La\(\mathrm{ div }\) operación produce el cociente, y la\(\bmod\) operación produce el resto, de la división entera\(b\div a\). En otras palabras,\(b ~ \mathrm{ div } ~ a=q\), y\(b\bmod a=r\).

Ejercicios 5.2

ejercicio\(\PageIndex{1}\label{ex:divalgo-01}\)

Buscar\(b ~ \mathrm{ div } ~ a\) y\(b\bmod a\), dónde

\(a= 13\),\(b= 300\)
\(a= 11\),\(b=-120\)
\(a=-22\),\(b= 145\)

ejercicio\(\PageIndex{2}\label{ex:divalgo-02}\)

Buscar\(b ~ \mathrm{ div } ~ a\) y\(b\bmod a\), dónde

\(a= 19\),\(b= 79\)
\(a= 59\),\(b= 18\)
\(a= 16\),\(b=-823\)
\(a=-16\),\(b= 172\)
\(a=- 8\),\(b=- 67\)
\(a=-12\),\(b=-134\)

ejercicio\(\PageIndex{3}\label{ex:divalgo-03}\)

Demostrar que\[b\bmod a \in\{0,1,2,\ldots,|a|-1\} \nonumber\] para cualquier número entero\(a\) y\(b\), donde\(a\neq0\).

ejercicio\(\PageIndex{4}\label{ex:divalgo-04}\)

Demostrar que entre tres enteros consecutivos cualquiera, uno de ellos es un múltiplo de 3.

Pista: Que los tres enteros consecutivos sean\(n\),\(n+1\), y\(n+2\). ¿Cuáles son los valores posibles de\(n\bmod3\)? ¿En qué se traduce esto, según el algoritmo de división? En cada caso, ¿qué sería\(n\)\(n+1\), y\(n+2\) parecería?

ejercicio\(\PageIndex{5}\label{ex:divalgo-05}\)

Demostrar que siempre\(n^3-n\) es un múltiplo de 3 para cualquier entero\(n\) por

Un análisis caso por caso.
Factoraje\(n^3-n\).

ejercicio\(\PageIndex{6}\label{ex:divalgo-06}\)

Demostrar que el conjunto\(\{n,n+4,n+8,n+12,n+16\}\) contiene un múltiplo de 5 para cualquier entero positivo\(n\).

ejercicio\(\PageIndex{7}\label{ex:divalgo-07}\)

Dejar\(m\) y\(n\) ser enteros tales que\[m ~ \mathrm{ div } ~ 5 = s, \qquad m\bmod5=1, \qquad n ~ \mathrm{ div } ~ 5 = t, \qquad n\bmod5=3. \nonumber\] Determine

\((m+n) ~ \mathrm{ div } ~ 5\)
\((m+n)\bmod5\)
\((mn) ~ \mathrm{ div } ~ 5\)
\((mn)\bmod5\)

ejercicio\(\PageIndex{8}\label{ex:divalgo-08}\)

Dejar\(m\) y\(n\) ser enteros tales que\[m ~ \mathrm{ div } ~ 8 = s, \qquad m\bmod8=3, \qquad n ~ \mathrm{ div } ~ 8 = t, \qquad n\bmod8=6. \nonumber\] Determine

\((m+2) ~ \mathrm{ div } ~ 8\)
\((m+2)\bmod8\)
\((3mn) ~ \mathrm{ div } ~ 8\)
\((3mn)\bmod8\)
\((5m+2n) ~ \mathrm{ div } ~ 8\)
\((5m+2n)\bmod8\)
\((3m-2n) ~ \mathrm{ div } ~ 8\)
\((3m-2n)\bmod8\)