Algoritmo De La División. Números Primos

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

Álgebra

Demostración:

Existencia: Sea Álgebra
. Este conjunto de enteros contiene elementos no negativos (por ejemplo, para n = - | a |), por lo que S*= S Álgebra
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 Álgebra
0 para algún entero q. Se tiene, por tanto, que a = qb+r con r Álgebra
0. Si r Álgebra
b, S* contendría al elemento no negativo a - (q+1)b = r - b < r que contradiceel hecho de que r es el primer elemento del conjunto S*. Por tanto, r < b.

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

Álgebra

Se tiene entonces que

Álgebra

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 Teorema1.4 el entero q recibe el nombre de cociente entero o simplemente cociente y el también entero r el de resto. Si dividimos por b obtenemos que a / b = q+ r / b con 0Álgebra
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Álgebra
a / b) y que denotaremos por Álgebra
. Esto facilita el cálculo de q. El de r se realiza posteriormentemediante 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 Álgebra
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 siguientecorolario:

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

Álgebra


Obsérvese que si b < 0 se tiene que a / b = q + r / b con 0 Álgebra
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 Álgebra
, es decir, el menor entero i tal que i Álgebra
a / b.

Definición 1.7. Si ay 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, o tambié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 cualquierentero 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 del propio 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 lassiguientes propiedades:

a | b y b | c Álgebra
a | c.

a | b y c | d Álgebra
ac | bd.

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

Si a Álgebra
0 y d | a Álgebra
| d |Álgebra
| a |.

Si c | a1, . . . , ak Álgebra
c | a1u1+ Álgebra
+ 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+ Álgebra
+akuk= q1cu1+ Álgebra
+ qkcuk = (q1u1 + Álgebra
+ qkuk) c

y dado que q1u1+ Álgebra
+qkuk Álgebra
Z , se tiene que c | (a1u1+ Álgebra
+ 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,...