7.2: El Algoritmo de División

Última actualización
Guardar como PDF

Page ID: 118365

Bob Dumas and John E. McCarthy
University of Washington and Washington University in St. Louis

\( \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}}\)

El Algoritmo de División, Teorema 7.11, es el resultado que garantiza que la división larga de los números naturales terminará en un cociente único y restará con el resto estrictamente más pequeño que el divisor. La división larga es difícil y tediosa para los jóvenes estudiantes. Por lo general, es el cómputo más desafiante que se espera que dominen los estudiantes de primaria. Es posible que hayas vuelto a visitar el algoritmo cuando aprendiste a dividir polinomios. Aquí el Algoritmo de División dice que el cociente y el resto son únicos y el resto es idéntico 0 o tiene grado estrictamente menor que el divisor. Frecuentemente comparamos la aritmética de enteros y la aritmética de polinomios, y es el Algoritmo de División el que hace útil esta comparación.

Extendamos el vínculo entre las combinaciones de enteros y los mayores divisores comunes. Según Lemma 7.2, un par de enteros son relativamente primos si hay una combinación entera del par que es igual a 1. Este resultado generaliza a los mayores divisores comunes distintos de\(1 .\)

TEOREMA 7.7. Vamos\(a, b \in \mathbb{Z}\). El conjunto de combinaciones enteras de a y\(b\) es igual al conjunto de múltiplos enteros de\(\operatorname{gcd}(a, b)\).

PRUEBA. Let\(c=\operatorname{gcd}(a, b)\) y\[M=\{k c \mid k \in \mathbb{Z}\} .\] Since\(c\) es un divisor de\(a\) y\(b\), hay\(i, j \in \mathbb{Z}\) tal que\[a=i c\] y\[b=j c .\] Let\[I=\{m a+n b \mid m, n \in \mathbb{Z}\} .\] Mostramos primero que \(I \subseteq M\).

Si\(m, n \in \mathbb{Z}\), entonces\[m a+n b=m i c+n j c=(m i+n j) c .\] De ahí cada combinación entera de\(a\) y\(b\) es un múltiplo de\(c\) y\[I \subseteq M .\] Ahora lo mostramos\(M \subseteq I\). Dejar\(k c \in M\) y\[r=\operatorname{gcd}(i, j) .\] Entonces hay\(m, n \in \mathbb{Z}\) tales que\[r m c=i c=a\] y\[r n c=j c=b .\] Así\(r c \mid a\) y\(r c \mid b\). De ahí\[\operatorname{gcd}(a, b) \geq r c \geq c .\] Sin embargo\(\operatorname{gcd}(a, b)=c\), y así\(r=1\). Por lo tanto\(i\) y\(j\) son relativamente primos.

Por la Proposición 7.2, hay una combinación entera de\(i\) y\(j\) que es igual a 1. Que\(u, v \in \mathbb{Z}\) sean tales que\[u i+v j=1 .\] Entonces\[c(u i+v j)=c\] y\[k c=k c(u i+v j)=k(u a+v b)\] por ecuaciones\(7.14\) y\(7.15\). De ahí\[k c \in I,\] y como\(k\) fue arbitrario,\[M \subseteq I .\] COROLARIO 7.8. Vamos\(a, b \in \mathbb{Z}\). Entonces\(\operatorname{gcd}(a, b)\) es la combinación entera positiva más pequeña de\(a\) y\(b\).

El teorema nos\(7.7\) dice que las combinaciones enteras de\(a\) y\(b\) son precisamente los múltiplos enteros de\(\operatorname{gcd}(a, b)\) (que resulta ser la combinación entera positiva más pequeña de\(a\) y\(b)\). Pensamos en\(\operatorname{gcd}(a, b)\) como “generar” a través de la multiplicación el conjunto de combinaciones enteras de\(a\) y\(b\). PROPOSICIÓN 7.9. Vamos\(a, b, k \in \mathbb{Z}\). Después\[\operatorname{gcd}(a, b)=\operatorname{gcd}(a-k b, b) .\] Prueba. Si\(c \in \mathbb{Z}, c \mid a\) y\(c \mid b\), entonces\(c \mid a-k b\). Por lo tanto\[\operatorname{gcd}(a, b) \leq \operatorname{gcd}(a-k b, b) .\] Del mismo modo\(c \mid b\), si\(c \mid a-k b\) y\(c \mid a\), entonces, así obtenemos la desigualdad inversa de (7.10), por lo que los dos lados son iguales.

TEOREMA 7.11. Algoritmo de división Let\(a, b \in \mathbb{Z}, b \neq 0\) Entonces hay únicos de\(q, r \in \mathbb{Z}\) tal manera que\[a=q b+r\] donde\(0 \leq r<|b|\).

Discusión. En el Algoritmo de División\(a\) se llama el dividendo,\(b\) el divisor,\(q\) el cociente, y\(r\) el resto.

Comprobante. Dejar\(a, b \in \mathbb{Z}\) y\(b \neq 0\). Definir\(I \subseteq \mathbb{N}\) por\[I=\{a-k b \mid k \in \mathbb{Z}\} \cap \mathbb{N} .\]\(I\) tiene un elemento más pequeño\(a-q b\),, para algunos\(q \in \mathbb{Z}\).

Reclamación:\(0 \leq a-q b<|b|\).

Comprobante de Reclamación

Argumentamos por casos.

Caso 1:\(b>0\)

Si\(a-q b \geq b\) entonces\[a-(q+1) b \geq 0 .\] De ahí\[a-(q+1) b \in I .\] Sin embargo\(a-q b\) es mínimo en\(I\), entonces esto es imposible. Por lo tanto\[a-q b<|b| \text {. }\] Caso 2:\(b<0\)

Si\(a-q b \geq|b|\), entonces\[a-q b>a-(q-1) b \geq 0 .\] Como en el primer caso\[a-(q-1) b \in I\] Esto es imposible ya que por suposición\(a-q b\) es mínima en\(I\). Por\[a-q b<|b|\] lo tanto, si\[r:=a-q b\] tenemos\(a=q b+r\) y\(0 \leq r<|b|\). Queda por demostrar que el cociente y el resto son únicos. Supongamos\[a=m b+r=n b+s\] dónde\(0 \leq r, s<|b|\). Si\(r=s\) entonces\(m b=n b\) y\(m=n\). Entonces asumimos eso\(r \neq s\). Sin pérdida de generalidad asumimos eso\(r<s\). Entonces,\[0 \leq s-r=(m-n) b<|b|\] Entonces\(m-n=0\) y\(r=s\), una contradicción.

Por supuesto,\(q\) y\(r\) podría encontrarse por división larga -es decir, se pueden restar múltiplos de\(b\) hasta que el resto sea menor que\(|b|\).