Algoritmo de la division

ALGORITMO DE LA DIVISIÓN.

Comenzaremos esta sección estudiando el algoritmo de la división que establece el siguiente teorema:

Teorema 1.4. [Algoritmo de la división] Si a y b son enteros con b > 0, existe un único par de enteros q y r tales que

Demostración:

•Existencia: Sea
. Este conjunto de enteros contiene elementos no negativos (por ejemplo, para n = - | a | ), por lo queS*= S
N es un subconjunto no vacío de N y, por tanto, de Z . El axioma de buena ordenación de los números enteros nos asegura la existencia de un primer elemento de S* que será de la forma r = a - qb
0 para algún entero q. Se tiene, por tanto, que a = qb+r con r
0. Si r
b, S* contendría al elemento no negativo a - (q+1)b = r - b < r que contradice el hecho de que r es el primer elemento delconjunto S*. Por tanto, r < b.

•Unicidad: Supongamos que existen dos parejas de enteros (q, r) y (q', r') tales que

Se tiene entonces que

lo que imposibilita el hecho de que | r - r' | < b. Por tanto, ha de ser q = q' y de ahí que también sea r = r', lo que prueba la unicidad.

Definición 1.5. Con la notación del Teorema 1.4 el entero q recibe el nombre de cociente entero osimplemente cociente y el también entero r el de resto. Si dividimos por b obtenemos que a / b = q+ r / b con 0
r / b < 1 por lo que q viene dado por la parte entera por defecto o suelo de a / b (el mayor entero i con i
a / b) y que denotaremos por
. Esto facilita el cálculo de q. El de r se realiza posteriormente mediante la igualdad r = a - qb.

Si consideramos ahora el caso b < 0, dado que -b >0, el Teorema 1.4 nos garantiza la existencia de los enteros q* y r tales que a = q* (-b) + r con 0
r < - b, y haciendo q* = - q se obtiene que a= qb+ r. La prueba de la unicidad es similar a la anterior.



Teniendo en cuenta este resultado y el del Teorema 1.4, podemos establecer el siguiente corolario:

Corolario 1.6. Si a y b son dos enteros con b
0, existe un único par deenteros q y r tales que



Obsérvese que si b < 0 se tiene que a / b = q + r / b con 0
r / b > -1 por lo que en este caso q es la parte entera por exceso o techo del cociente a / b que denotaremos por
, es decir, el menor entero i tal que i
a / b.

Definición 1.7. Si a y b son enteros y a= qb para algún entero q, diremos que b divide a a, o bien que b es un factor o un divisor de a, otambién que a es múltiplo de b.

Así, por ejemplo, los factores de 6 son ±1, ±2, ±3 y ±6. Cuando b divide a a lo denotaremos por b | a. Para evitar errores obsérvese que cualquier entero divide a 0 (ya que 0 = 0 · b para cualquiera que sea el entero b), 1 divide a cualquier entero y cualquier entero se divide a si mismo. Debido a ello, dado un entero n, sólo los divisores de n distintos de 1 y delpropio n se consideran divisores propios de dicho número.

Recordamos a continuación algunas propiedades simples pero útiles de la divisibilidad, probando dos de ellas y dejando la demostración de las otras a modo de ejercicios para el alumno.

Teorema 1.8. Se verifican las siguientes propiedades:

•a | b y b | c
a | c.

•a | b y c | d
ac | bd.

•Si m
0
a | b si, y sólo si,ma | mb.

•Si a
0 y d | a
| d |
| a |.

•Si c | a1, . . . , ak
c | a1u1+
+ akuk cualesquiera que sean los enteros u1, . . . , uk.

•a | b y b | a si, y sólo si, a = ± b.

Demostración: (Se demostrarán aquí, solamente las propiedades 5 y 6).

•Si c | ai se tiene que ai = qi c para algunos enteros qi (i=1,2, . . . , k). Entonces

a1u1+
+akuk= q1cu1+
+ qkcuk = (q1u1 +
+qkuk) c

y dado que q1u1+
+qkuk
Z , se tiene que c | (a1u1+
+ akuk).

•Si a = ± b se tiene que b = qa y a = q'b donde q = q' = ± 1, por lo que a | b y b | a.

Recíprocamente, si a | b y b | a es b = qa y a = q'b para algunos enteros q y q'. Si b = 0, de la segunda igualdad se obtiene que a = 0, por lo que a = ± b. Podemos suponer, por tanto, que b
0. Eliminando a de ambas...