1.5: El algoritmo de división
- Page ID
- 117407
El objetivo de este capítulo es introducir y probar el siguiente resultado importante.
Si\(a\) y\(b\) son enteros y\(b>0\) entonces existen enteros únicos\(q\) y\(r\) satisfaciendo las dos condiciones:\[\label{divalg} a=bq+r\quad\text{and}\quad 0\le r<b. \]
En esta situación\(q\) se llama cociente y\(r\) se llama el resto cuando\(a\) se divide por\(b\). A veces nos referimos\(a\) como el dividendo y\(b\) como el divisor.
(Se debe tener cierto cuidado con este último término, a la luz de cómo se definió el divisor de un entero en la Sección 1.4. Es correcto tanto decir que 2 no es un divisor de 7, ya que\(2 \nmid 7\), aunque 2 es el divisor cuando 7 se divide por 2, cediendo\(7 = 2\cdot 3 + 1\). El contexto debe dejar claro cuál es el significado que se pretende.)
Tenga en cuenta que hay dos partes en la declaración del Algoritmo de División. Una parte es la existencia de enteros\(q\) y\(r\) satisfactorios\(\eqref{divalg}\), y la segunda parte es la singularidad de los enteros\(q\) y\(r\) satisfactorios\(\eqref{divalg}\).
Prueba
Primero probamos la existencia de\(q\) y\(r\).
Si\(b\) divide\(a\) entonces\(a=kb\) para algún entero\(k\), y podemos escribir\(q=k\) y\(r=0\).
Supongamos que en cambio eso\(b\) no divide\(a\), y considera la colección\[\dots, \; a-3b, \; a-2b, \; a-b, \; a, \; a+b, \; a+2b, \; a+3b, \; \dots\nonumber \] de enteros. \(S\)Sea el conjunto de todos estos números que no son negativos. En símbolos,\[S = \{a-kb \mid k \in \mathbb{Z}\, \text{ and }\, a-kb\geq 0\}.\nonumber \]
El conjunto no\(S\) está vacío, ya que por la Propiedad de Arquímedes existe un número natural\(n\) tal que\(n>-a\) y así\(nb \geq n > -a\) y por lo tanto\(a-(-n)b > 0\). Ahora por el Principio de Ordenamiento del Bien\(S\) contiene un elemento más pequeño; llámalo\(r\). Por nuestra definición de\(S\), esto significa que para algún entero en particular\(q\) tenemos\(r=a-qb\). Así\(a = bq+r\), y sólo queda por demostrarlo\(0 \leq r < b\).
Todos los elementos de\(S\) son positivos, por lo que es claro que\(0 \leq r\). Si no es cierto eso\(r < b\), entonces\(a-bq \geq b\) y así\(r-b = a-(q+1)b \geq 0\); así o\(r-b\) es un elemento de\(S\) o\(r-b=0\). Ya que se\(r\) definió como el elemento más pequeño de\(S\), no puede ser cierto que\(r-b\) está en\(S\). No obstante, si\(r-b=0\), entonces\(a = bq+b = (q+1)b\), lo que contradice nuestra suposición que\(b\) no divide\(a\). Nos vemos obligados a concluir eso\(0 \leq r < b\).
Todavía tenemos que demostrarlo\(q\) y\(r\) estamos determinados de manera única. Para ello suponemos que\[a=bq_1+r_1\quad\text{and}\quad 0\le r_1<b,\nonumber \] y\[a=bq_2+r_2\quad\text{and}\quad 0\le r_2<b\nonumber \] para enteros\(q_1,q_2,r_1,r_2\). Debemos demostrar eso\(r_1=r_2\) y\(q_1=q_2\). Si\(r_1\neq r_2\) sin pérdida de generalidad podemos asumir eso\(r_2>r_1\). Restar estas dos ecuaciones obtenemos\[0=a-a=(bq_1+r_1)-(bq_2+r_2)=b(q_1-q_2)+(r_1-r_2).\nonumber \] Esto implica que Esto implica que\[ \label{equation5.1} r_2-r_1 = b(q_1-q_2).\] esto implica\(b\mid r_2-r_1\). Por Teorema 1.4.1 (10) esto implica que\(b\le r_2-r_1\). Pero ya\[0 \le r_1 < r_2 < b\nonumber \] que tenemos\(r_2-r_1<b\). Esto contradice\(b\le r_2-r_1\). Por lo que debemos concluir eso\(r_1=r_2\). Ahora desde\(\eqref{equation5.1}\) que tenemos\(0=b(q_1-q_2)\). Ya que\(b>0\) esto nos dice que\(q_1-q_2=0\), es decir,\(q_1=q_2\). Esto completa la prueba de la singularidad de\(r\) y\(q\) en\(\eqref{divalg}\).
En teoría de números solemos preferir trabajar con enteros, pero si estamos dispuestos a considerar la división de números reales, se puede demostrar que cuando\(a\) se divide por\(b\), el cociente y el resto satisfacen\[q = \left \lfloor \frac{a}{b} \right \rfloor \qquad \text{and} \qquad r = a - bq = a - b\left \lfloor \frac{a}{b} \right \rfloor\nonumber \] (ver Ejercicio\(\PageIndex{2}\)).
Pasamos ahora a algunos conceptos familiares.
Un entero\(n\) es par si\(n=2k\) para algunos\(k\), y es impar si\(n=2k+1\) para algunos\(k\).
Por la paridad de un entero nos referimos a si es par o impar.
A veces un problema en la teoría de números se puede resolver dividiendo los enteros en varias clases dependiendo de sus restos cuando se dividen por algún número\(b\). Por ejemplo, esto es útil para resolver Ejercicios\(\PageIndex{5}\) y \(\PageIndex{6}\)al final de este capítulo.
Para\(b>0\) definir\(a\bmod b\) como el valor de\(r\) en el par\(q,r\) satisfaciendo las expresiones\(a=bq+r\) y\(0\le r<b\).
En otras palabras,\(a \bmod b\) es el resto dado por el Algoritmo de División cuando\(a\) se divide por\(b\).
Por ejemplo\(23\bmod 7=2\) desde\(23=7\cdot 3+2\) y\(-4\bmod 5=1\) desde entonces\(-4=5\cdot (-1)+1\).
Tenga en cuenta que algunas calculadoras y la mayoría de los lenguajes de programación tienen una función a menudo denotada por\(MOD(a,b)\) o\(mod(a,b)\) cuyo valor es lo que acabamos de definir como\(a\bmod b\). Cuando este es el caso los valores\(r\) y\(q\) en el Algoritmo de División para dado\(a\) y\(b>0\) están dados por\[\begin{aligned} r &=a \bmod b \\ q &=\frac{a-(a \bmod b)}{b}\end{aligned}\] Si también la función floor está disponible tenemos\[\begin{aligned} r &=a \bmod b \\ q &=\left \lfloor a/b \right \rfloor\end{aligned}\]
Ejercicios
Encuentre los valores de\(q\) y\(r\) en el Algoritmo de División para los siguientes valores de\(a\) y\(b\):
- Dejar\(b=3\) y\(a=0,1,-1,10,-10\).
- Dejar\(b=345\) y\(a=0,-1,1,344,7863,-7863\).
Dados enteros\(b > 0\) y\(a\), let\(q\) y\(r\) ser el cociente y resto cuando\(b\) se divide por\(a\), entonces\(a = bq+r\). Demostrar cuidadosamente que\[q = \left \lfloor \frac ab \right \rfloor.\nonumber \]
Usando el Algoritmo de División, demuestre que cada entero es par o impar, pero nunca ambos.
Demostrar\(n\) y tener\(n^2\) siempre la misma paridad. Es decir,\(n\) es aunque y sólo si\(n^2\) es par.
Mostrar que para todos los enteros\(n\) el número\(n^3-n\) siempre tiene 3 como factor.
(Pista: por el Algoritmo de División, cada entero\(n\) cae en uno de tres casos:\(n=3k\),\(n=3k+1\),\(n=3k+2\). Demostrar que\(n^3-n\) es divisible por 3 para cada uno de estos casos por separado.)
Mostrar que el producto de cualquiera de tres enteros consecutivos tiene 6 como factor. (¿Cuántos casos deberías usar aquí?)
Demostrar lo siguiente:
- Si\(b>0\) y\(b \mid a\), entonces\(a \bmod b=0\).
- Si\(b>0\) y\(a \bmod b=0\), entonces\(b \mid a\).
Calcula lo siguiente:
- \(0\bmod 10\)
- \(123\bmod 10\)
- \(10\bmod 123\)
- \(457\bmod 33\)
- \((-7) \bmod 3\)
- \((-3) \bmod 7\)
- \((-5) \bmod 5\)
- Utilice el algoritmo de división para probar el siguiente teorema similar: Si\(b > 0\) entonces para alguno\(a\) existe enteros únicos\(p\) y\(s\) tal que\[a=bp+ s\quad\text{and}\quad \left \lfloor -b/2 \right\rfloor < s \leq \left\lfloor b/2 \right \rfloor.\nonumber \]
- Encuentra enteros\(p\) y\(s\) tal que\(a=bp+s\) y\(\left \lfloor -b/2 \right\rfloor < s \leq \left\lfloor b/2 \right \rfloor\) para
- \(a=36, b = 13\)
- \(a=75, b=50\)
- \(a=75, b = 49\).