Algoritmo de la División

El Algoritmo de la División

Es momento de iniciar con algunas de las propiedades de divisibilidad de los números enteros. El siguiente es un teorema fundamental en la construcción de la teoría para este curso. En lenguaje coloquial este afirma que dado un entero $a$ este puede ser dividido por un entero positivo $b$ de tal manera que el residuo es más pequeño que $b$.

Teorema (El algoritmo de la división). Dados enteros $a,b$ con $b>0$, existen enteros únicos $q,r$ tales que:

(1)
\begin{align} a=qb+r \quad 0\le r < b. \end{align}

Los enteros $q$ y $r$ son llamados, respectivamente, el cociente y el residuo de la división de $a$ por $b$.

Demostración: Consideremos el conjunto $C$ de enteros de la forma $xs-b$ que son positivos para $x\in \mathbb{Z}$. Es decir:

(2)
\begin{align} C=\left\{ a-xb : x \in \mathbb{Z}\ \land\ a-xb \ge 0 \right\} \end{align}

Notemos que como $b\ge 1$, entonces tenemos que $| a |b \ge a$ y entonces

(3)
\begin{align} a-(-| a |)b = a+ | a |b \ge a + | a | \ge 0. \end{align}

por lo que $a-(-| a |)b \in C$ y por lo tanto $C\ne \emptyset$. Por el principio del buen orden, $C$ tiene un primer elemento, digamos $r\in C$, entonces por definición de $C$, existe un entero $q$ tal que $r=a-qb$. Afirmamos que $r<b$, en efecto, si suponemos lo contrario, es decir si $r\ge b$ entonces

(4)
\begin{align} a - (q+1)b = (a-qb) -b = r-b \ge 0 \end{align}

estaría en $C$, pero este elemento es menor que $r$ lo cuál no es posible por la elección de $r\in C$ come el primer elemento.

Ahora queremos demostrar que estos enteros son únicos. Supongamos que $a$ tiene dos representaciones en la forma deseada, es decir supongamos que

(5)
\begin{align} a= qb+r = q'b+r'\quad {0\le r, r' < b }. \end{align}

Entonces $|r-r'| = b | q-q' |$, pero también $-b \le r-r' \le b$, es decir $| r-r' | <b$ y por lo tanto $| q-q' | < 1$ dejando como única posibilidad $q=q'$ y por lo tanto $r=r'$. $Q.E.D$.

Como corolario tenemos una versión más general del algoritmo de la división, que es obtenido al quitar la restricción $b>0$ pero simplemente pidiendo $b\ne 0$.

Corolario: Si $a,b\in \mathbb Z$ con $b\ne 0$, entonces existe enteros $q,r$ únicos con la propiedad de que $a=qb+r$ con $0\le r \le | b |$.

Demostración: Por el resultado anterior, basta considerar el caso $b<0$. Si aplicamos el resultado anterior para $a, | b |$ tenemos que existen enteros $q,r$ tal que $a= q | b | + r$ con $0\le r <| b |$. Pero como $| b | = -b$ tenemos que $a = (-q)b +r$ es una expresión en la forma deseada. $Q.E.D$

Ejemplo: Sea $a= 1, -2, 61, -59$ y tomemos $b= -7$. Entonces en cada caso tenemos:

(6)
\begin{align} 1 = 0(-7)+1\\ -2 = 1(-7) + 5\\ 61 = (-8)(-7)+ 5 \end{align}

Algunas consecuencias inmediatas del algoritmo de la división son las siguientes: Cuando el divisor es $b = 2$ entonces el residuo del algoritmo de la división es o 0 o 1. Decimos que $a$ es par si el residuo al dividir entre dos es 0, y que $a$ es impar si el residuo es uno. Así todo número impar es de la forma $a=2k +1$ y todo número par es de la forma $a=2k$. Así si tomo un entero $a$ es de la forma $2k \text o \ 2k+1$. Si nos fijamos ahora en $a^2$ entonces este es de la forma $(2k)^2 = 4k$ o bien de la forma $(2k+1)=2 = 4k^2 + 4k +1 = 4(k2+k)+1$ y podemos concluir que el residuo de número entero al dividirlo entere cuatro es o cero o uno. ¿ Es 2014 un número cuadrado? al dividir este número entre 4 vemos que deja residuo 2, por lo tanto 2014 no es un cuadrado.

Ejercicio: Demuestra que el cuadrado de un número impar deja residuo 1 al dividirlo entre 8.

Ejercicio: Muestra que todo entero de la forma $6k+5$ es también de la forma $3k+2$ pero que el converso no es necesariamente cierto.

Ejercicio: Usa el algoritmo de la division para mostrar que:

Ejercicio: Prueba que para $n\ge 1$ se tiene que $n(n+1)(2n+1)/6$ es un entero.

Definición: Sean $a,b$ enteros. Decimos que $a$ divide a $b$ (y lo denotamos por $a|b$), si existe un entero $c\in \mathbb{Z}$ tal que $b=ac$. También decimos que $b$ es divisible por (o entre) $a$. También decimos que $a$ es un divisor de $b$ o que $a$ es un factor de $b$ o que $b$ es un múltiplo de $a$. Escribimos $a\nmid b$ si $a$ no divide a $b$.

Por ejemplo $-12$ es divisible por $3$ pero 21 no es divisible por 5

Proposición: Se cumplen las siguientes propiedades:

  • $a|a$
  • $a| 1$ si y sólo sí $a=\pm 1$
  • $a|b \rightarrow a | -b$
  • $a|b, b|d \rightarrow a|d$
  • $a|b \rightarrow a|bd$ para todo $d\in \mathbb{Z}$
  • $a| b, c|d \rightarrow ac | bd$
  • Si $a|b$ y $b\ne 0$ entonces $| a | \le | b |$
  • $a| b,\ a|d \rightarrow a| (b\pm d)$
  • Si $a|b, a|c \rightarrow a | (bx+cy)$ para todos enteros $x,y$
  • Si $a|b$ y $b|a$ entonces $a=\pm b$.

De la definición anterior se sigue que $0| 0$ pero $0$ no divide a ningún otro entero. También todo entero $a|0$ y $1, -1$ dividen a todo entero.

Ejemplo: Qué números dividen a $n$ y a $2n+5$ simultáneamente?

Corolario: Sea $a\ne 0$. $a|b$ si y sólo si el residuo al dividir $b$ entre $a$ es cero, es decir si al aplicar el algoritmo de la división $b=aq+r$, $r=0$.

Ejercicio: Prueba por inducción que si $a|b_k$ para $k= 1,2,\ldots,n$ entonces $a| b_1x_1 + b_2 x_2 + \ldots + b_n x_n$ para cualesquiera enteros $x_k, k=1,\ldots,n.$.

Si $a, b$ son enteros arbitrarios, enteonces un entero $d$ es llamado un divisor común de $a$ y $b$, si $d|a \land d|b$. Como $1$ es un divisor de todos los enteros, entonces el conjunto de divisores comunes de $a,b$ es no vacío. Cuando alguno $a \lor b$ es distinto de cero, el conjunto de divisores comunes positivos es finito. Dentro de estos, hay uno que es el mayor, este es llamado el máximo común divisor de $a$ y $b$.

Definición: Sean $a,b\in \mathbb{Z}$ con al menos uno distinto de cero. El máximo común divisor de $a$ y $b$ denotado por $(a,b) =mcd(a,b)$, es el entero positivo $d$ que satisface:

  • $d|a$ y $d|b$
  • Si $c|a$ y $c|b$ entonces $c\le d$.
Si no se indica lo contrario, el contenido de esta página se ofrece bajo Creative Commons Attribution-ShareAlike 3.0 License