Algoritmo de euclides

APENDICE

Teorema 1 (Algoritmo de la división).

Sean a, b enteros con b positivo. Entonces existen enteros únicos q, r, tales que
a=bq+r con 0 ≤r<b

Demostración
1. Existencia:
Sea S= a-bxx ∈Z y a-bx≥0. S≠Ø puesto que si a ≥0, a-b0=a ∈S. Si a<0 como b≥1 tenemos que a-ab=a(1-b)≥0 y asi a-ab∈S.
Usando el Principio de la Buena Ordenación, S tiene un mínimo r y enconsecuencia existe un entero q tal que
a-bq=r con 0≤r
De otra parte, puesto que r = min S, entonces
r-b=a-bq-b=a-q+1b<0
Y por tanto r<b
2. Unicidad:
Supongamos que a=bq+r=bq'+r'con 0≤r<b y 0≤r'<b. Si suponemos que q'<q entonces q'+1≤q y por tanto
r=a-bq≤a-bq'+1=a-bq'-b=r'-b<0,
Que evidentemente es una contradicción. Análogamente para el caso q<q' luego necesariamente q=q' ytambién r=r'.

Máximo Común Divisor

Definición: Sean a y b enteros no nulos, el conjunto de todos los divisores comunes de a y b es un conjunto finito cuyo máximo se denomina Máximo común divisor de a y b. Suele denotarse como MCD(a,b) o (a,b)

Teorema 2. Sean a y b enteros no nulos. El MCD(a,b) es el menor entero positivo que pueda escribirse en la forma ax + by con x, y enteros.Demostración:
Supongamos que d=(a,b) y sea
S= z ∈ Z+z=ax+by con x, y ϵ Z
S ≠ Ø puesto que a2+ b2 ∈S. Luego por el Principio de la buena Ordenación, S posee un mínimo g que podemos escribir de la forma g=ax0+by0. Es claro que g es divisor común de a y b, puesto que si usamos el algoritmo de la división entre a y g tenemos:
a=qg+r con 0≤r <g
Luego,
r=a-qg
=a-qax0+by0
=a1-qx0+b(-qy0)=ax'+by'
Ahora, si r≠ 0, entonces r ∈ S, lo cual contradice el hecho que g sea mínimo, por tanto r = 0 , g| a y g| b.
Como d = (a,b) y g es divisor común entonces g ≤d. De otra parte, g=ax0+by0 y d| a d| b luego d| g y como ambos son números positivos d≤g y en consecuencia d=g.

Teorema 3. (Propiedades del MCD)
Sean a y b enteros no nulos. Entonces d = (a,b) si y solamente si d satisfacelas siguientes propiedades:
1. d > 0

2. d| a y d| b

3. Si f| a y f| b entonces f| d

Demostración:
Supongamos que d= (a,b). Es evidente que d > 0 y que d| a y d| b. Además d = ax + by para algún par de enteros x, y y si f| a y f| b entonces f divide a toda combinación lineal de a y b, f| ax+by, en especial f| d.
Recíprocamente supongamos que d satisface (1), (2) y (3) ysupongamos que f es divisor común de a y b; entonces por (3) f| d y en consecuencia f≤ d=d, luego d es el mayor de los divisores comunes de a y b.

Teorema 4. Si a=bq+r entonces (a,b) = (b,r)

Demostración:
Supongamos que d = (a,b) y d’ = (b,r). Como d| a y d| b entonces d| r=a-bq, en consecuencia d| d'. Análogamente d'| a=bq+r y en consecuencia d'| d. Dado que d y d’ son positivos entoncesd = d’

Teorema 5.
ALGORITMO DE EUCLIDES
Este procedimiento permite calcular el MCD de dos enteros dados a y b. Fue presentado por Euclides (365- 300 A.C) en el séptimo libro de Los Elementos:
Sean a, b dos enteros positivos tales que b ł a. Se escribe r0=a, r1=b y aplicamos repetidamente el algoritmo de la división obteniendo un conjunto de restos r2,r3,…,rn,rn+1 definidos sucesivamente porlas relaciones
r0=r1q1+r2 0 <r2<r1
r1=r2q2+r3 0 <r3<r2
...
rn-2=rn-1qn-1+rn 0 <rn<rn-1
rn-1=rnqn+rn+1 rn+1=0
Entonces rn, el último resto no nulo de este proceso, es (a,b), es decir el mcd de a y b.

Demostración 1:
Existe un momento en el que rn+1 =0 puesto que los ri son decrecientes y no negativos. La ultima relación, rn-1= rnqndemuestra que rn|rn-1. La anterior a la última, prueba que rn|rn-2. Por inducción vemos que rn divide a cada ri. En particular rn|r1=b y rn|r0=a, luego rn es un divisor común de a y b. Ahora sea d otro divisor común de a y b. La definición de r2 prueba que d|r2. La relación que le sigue prueba que d|r3. Por inducción, d divide a cada ri luego d|rn. Por lo tanto rn es el MCD.
Demostración 2:...