Divisibilidad. El algoritmo de Euclides.

Divisibilidad: divisores y múltiplos. El teorema de la división.

Dados dos números enteros a y b (con a distinto de 0), se dice que a divide a b, y lo escribimos como a|b,si existe un c∈Z tal que b= ac.

También se dice que a es un factor o divisor de b, y que b es un múltiplo de a.

Algunas propiedades derivadas de la definición anterior:

1|a
a|0
a|b y a|c ⇒ a|b+c
a|b y a|c ⇔ a|bx+cy para cualesquiera x, y∈ Z
a|b y b|a ⇒ a = b o bien a = -b

Teorema de la división.

Sean a∈ Z y b∈ N. Entonces existen q, r∈ Z con 0< r <b tales que a=bq+r. Además, q y r son únicos.

Esta es la vieja fórmula de la división entera: dividendo a es igual al divisor b multiplicado por el cociente q, más un resto r.

Sistemas de numeración

Una consecuencia importante del teorema de la división, es que nos sirve para justificar el método habitual en que representamos los números enteros (i.e. mediante un sistema de representación posicional).

Sea t > 2 un entero al que llamamos la base de cálculo. Para cualquier entero x tenemos, aplicando el teorema de la división dividiendo repetidamente el entero x por nuestra base t,

x = tq₀ + r₀
q₀ = tq₁ + r₁
....
q_n-2 = tq_n-1 + r_n-1
q_n-1 = tq_n + r_n

cada resto r_i es uno de los enteros 0,1,...,t-1, y se termina la serie cuando q_n=0. Si eliminamos los cocientes q_i , se obtiene que

x = r_ntⁿ + r_n-1t^n-1 +...+ r₁t + r₀

Puede así verse como podemos representar o expresar x en la base t, mediante la sucesión de restos obtenida, y lo escribimos como x = (r_nr_n-1...r₁r₀)_t

Esta representación del número entero x es además única para la base t

Cuando la base es t=10, decimos que estamos usando notación decimal. A la notación en base 2 se le llama binaria, a la notación en base 16 se le llama hexadecimal y a la notación en base 8 se le llama octal. La base 10 es la notación convencional para calcular habitualmente, y es por eso que en el caso decimal omitiremos el subíndice t al representar el número.

Ejemplo en sistema decimal: 1970 = (1x10³) + (9x10²) + (7x10) + 0
Ejemplo en sistema octal: (3662)₈ = (3x8³) + (6x8²) + (6x8) + 2 = 1970
Expresar el decimal 220 en el sistema binario. Dividiendo sucesivamente por la base 2:

220 = 2.110 + 0
110 = 2.55 + 0
55 = 2.27 + 1
27 = 2.13 + 1
13 = 2.6 + 1
6 = 2.3 + 0
3 = 2.1 + 1
1 = 2.0 + 1

Por tanto 220 = (11011100)₂

Aplicación de ejemplo: Conversión de un número decimal (base 10) a otra base

Máximo común divisor. El algoritmo de Euclides.

El máximo común divisor de dos enteros

Dados dos enteros a y b distintos de 0, decimos que el entero d>1 es un máximo común divisor, o mcd, de a y b si

d|a, d|b y para cualquier otro c ∈ Z tal que c|a y c|b, entonces c|d

Es decir, d es un entero positivo, divisor común de a y b, y cualquier otro divisor común es también un divisor de d.

Con estas condiciones, el máximo común divisor es único. Se denota por d= mcd(a,b)

Algunas propiedades del máximo común divisor

mcd(a,b) = mcd(|a|,|b|)
mcd (ka,kb) = |k| mcd(a,b)
Si a|b.c y mcd (a,b) =1, entonces a|c
mcd(a,b) = d ⇔ d|a, d|b y mcd(a/d , b/d)=1

El algoritmo de Euclides

Proposición

Sean a,b enteros no nulos. Entonces mcd(a,b) = mcd(b,r) donde r es el único 0<r<b tal que existe un entero q con a= bq + r (esto es, que r es el resto de la división de a por b)

Esta proposición nos indica que es igual de válido calcular el mcd(a,b) que el mcd(b,r), con la ventaja de que r es un entero de menor tamaño que el original a. Esto es aprovechado por el algoritmo de Euclides para el cálculo del máximo común divisor de dos números enteros.

El algoritmo de Euclides

Para calcular el mcd de dos enteros a y b (ambos >0, suponemos a > b) se definen q_i y r_i recursivamente mediante las ecuaciones:

a = bq₁ + r₁  (0<r₁<b)
b = r₁q₂ + r₂  (0<r₂<r₁)
r₁ = r₂q₃ + r₃  (0<r₃<r₂)
....
r_k-3 = r_k-2q_k-1 + r_k-1  (0<r_k-1<r_k-2)
r_k-2 = r_k-1q_k  (r_k=0)

Y de la proposición anterior, se sigue que:

mcd(a,b) = mcd(b,r₁) = mcd(r₁,r₂) = ... = mcd(r_k-2,r_k-1) = r_k-1

Además se puede demostrar que el número de pasos necesarios para calcular el mcd de dos números es menor que 5 veces el número de dígitos del menor de ellos.

A continuación, figura una posible implementación en pseudocódigo del algoritmo de Euclides:

Algoritmo de Euclides

Observación

Sean a,b enteros no nulos, y sea d = mcd(a,b). Entonces d es el menor entero positivo (no nulo) que puede expresarse en la forma ax + by con x,y∈ Z

Una propiedad del algoritmo de Euclides:

El algoritmo de Euclides también nos proporciona un método para calcular dos valores enteros x e y tales que mcd(a,b) = ax + by. Este método consiste en ir despejando el resto de la última división, el que nos da el valor mcd(a,b), hacia atrás hasta llegar a los valores a y b de partida.

Corolario: primos relativos

Sean a,b enteros no nulos. Entonces mcd(a,b) = 1 si y solo si existen enteros s y t tales que as + bt = 1. Se dice en este caso que a y b son números primos entre sí, o que son primos relativos, o simplemente que a es primo con b (y viceversa).

Aplicación de ejemplo: El Algoritmo de Euclides

Ecuaciones diofánticas

Las ecuaciones de la forma ax + by = c con a,b,c ∈ Z\{0}, y con raíces enteras, se conocen como ecuaciones diofánticas de primer grado, llamadas así por Diofanto

de Alejandría, matemático griego a quien se considera el padre del álgebra.

Lema de Euclides

Sean a, b, c∈Z con mcd(a,b)=1, tales que a|bc. Entonces se puede afirmar que a|c. (Es decir, si a y b son primos entre sí, y a es un divisor de bc, entonces a es divisor de c)

Teorema

La ecuación diofántica ax + by = c, con a, b, c∈Z\{0} tiene soluciones enteras si y sólo si d|c, siendo d el mcd(a,b). Además, la solución general de esta ecuación es de la forma:

x = x₁ + (tb / d)

y = y₁ - (ta / d)

para todo valor t entero, en donde (x₁, y₁) es una solución particular cualquiera de la ecuación ax + by = c (que puede obtenerse, por ejemplo, a partir del algoritmo de Euclides).