10.2 Máximo común divisor.

Definición 1.3 Dados dos números a y b no negativos y no ambos cero el mayor número que divide a los dos se denomina máximo común divisor de a y b. Denotamos a este número como(a,b). En general, dado un conjunto de enteros no negativos y no todos cero{a₁,a₂...a_n}, definimos a su máximo común divisor (a₁,a₂....a_n)como el mayor entero positivo que los divide a todos.
La definición anterior implica que (a,b) siempre es positivo. Algunas propiedades básicas son:
1.-(a,1) =1 para toda a
2.-(a,a) =a para toda a.
3.-(a,0) =a para toda a.
4.-(a,b) = (b,a).
5.-(a,b) = (b, a-b).
Para probar la última propiedad notemos que si un número divide a a y b, divide a a-b por lo que es un divisor común de b y a-b. A la inversa si divide a b y a a-b divide a (a-b)+b=a. Esto implica que los divisores comunes de a y b son los mismos que los de b y a-b y por tanto el mayor de ambos conjuntos es el mismo número.
Esta propiedad también nos permite calcular el MCD de dos números dados. Por ejemplo, sean a= 26, b = 10. Entonces
(26,10)=(10,16)=(16,10)=(10,6)=(6,4)=(4,2)=2
Estas cuentas se pueden acelerar mediante el uso del algoritmo de la división. Si a =bq + r con o ≤ r < b (entonces (a,b)=(b, a-bq)= (b,r) se deja la prueba de estas igualdades al lector. Así como 26 = 10 × 2 +6 el cálculo anterior se convierte en:
(26,10)= (10,6) =(6,4) =(4,2) = 2.
El proceso arriba mencionado se conoce como algoritmo de Euclides.

(Teorema 10.7) Si g es el máximo común divisor de a y b, entonces existen enteros u,v tales que g =au +bv..
Prueba Consideremos el conjunto de todos los números de la forma ax +by con x,y enteros (el conjunto de combinaciones lineales de a y b). De este conjunto escojamos el menor enteo positivo y llamémosle d. Sean u,v tales que d = au +bv. Si



aplicamos el algoritmo de la división a = dq +r con 0 < r < d. Pero
r=a – dq=a- (au +bv)q =a(1-qu) +b (-qv)
Significa que r es positivo, está en el conjunto y es menor a d. Esto es una contradicción ya que habíamos supuesto que d era el menor número positivo del conjunto. Por tanto. d | a. Por un argumento similar obtenemos que d |b.
Ahora sea g el máximo común divisor de a y b. Como g |a y g | b, g | au +bv. Si g ≠ d tendríamos que g < d, es decir g no era el mayor de todos los divisores comunes de a y b, lo cual es una contradicción, concluimos pues ,que g=d.


Corolario 10.8 El máximo común divisor de a y b es la combinación lineal positiva más pequeña de ambos.
Corolario 10.9 = Si (a,b)=1 , la ecuación ax + by =1 tiene solución entera.
Prueba . Hállese los enteros x, y para los que (a,b) = ax +by.
Corolario 10.10 (a, a +a) =1.
Prueba (-1) × a +(1) × (a-1)=1. Entonces 1 es la combinación lineal positiva más pequeña y por lo tanto igual a (a,a +1).
Teorema 10.11 (am,bm) = m(a,b).
Prueba. (am,bm) es el menor valor positivo de amx + bmy = m (ax +by). Esto es lo mismo que m veces el menor valor positivo de ax +by el cual es a,b).
Corolario 1.12 Si d = (a,b) entonces








Otra manera de caracterizar l máximo común divisor de a y b es como sigue. Supongamos que d es cualquier divisor común de a y b. Entonces d divide a cualquier combinación lineal de a y b. , en particular divide a la menor positiva es decir, es decir divide a (a,b). Y como a |b implica a ≤ b, (a,b) es el único número con esta propiedad. Lo cual prueba el siguiente teorema.
Teorema 10.13 El máximo común divisor de a y b es el único entero positivo que es divisible entre cualquier número que divida tanto a a como a b.
Definición 10.4 Dados dos números a, b decimos que son primos relativos, si (a,b)= 1. En general, decimos que un conjunto (x₁,x₂,...x_n) de enteros son primos relativo entre si cuando (x₁,x₂,...x_n)=1.
Definición 10.5 dado un conjunto {x ₁,x,₂...x_n } de enteros, decimos que son primos relativos dos a dos si (x_i,x_j)=1 para cualquier pareja x_i,x_j.
Ser primos relativos entre sí y ser primos relativos dos a dos no es lo mismo. Por ejemplo, los números 4,6,9 son primos relativos entre sí puesto que (4,6,9)= 1, pero no son primos relativos dos a dos ya que (4,6)=2.
A continuación se enuncia no de los resultados más usados en relación al máximo común divisor y a la vez uno de los más fuertes, ya que será pieza clave en la demostración del Teorema fundamental de la aritmética.
Teorema 10.14 Si c |ab y (c,a)=1 entonces c |b.
Prueba. Como c |ab y c| bc, c |(ab, bc) .Pero (ab,bc)= b (a,c)= b. Por tanto, c| ab.
Un caso muy especial se obtiene cuando c es primo.
Teorema 10.15
Si p es primo y divide a ab, y p no divide a a entonces p divide a b.
Prueba sea d = (a,p). Entonces d |p por lo tanto d solo puede ser 1 o p . Como
Tenemos que d≠ p y por lo tanto d =1. Aplicando el teorema anterior llegamos a que p| b.
Teorema 10.16 (Teorema fundamental de la aritmética) Todo número se puede factorizar de manera única como producto de primos.
Prueba. Ya hemos probado que todo número se puede factorizar en primos, y nos resta probar la unicidad de esta factorización. Sean

dos factorizaciones distintas donde por conveniencia suponemos que los primos aparecen listados en orden creciente. Cada p_i divide a n y por tanto a alguna q_j(aplicando varias veces el argumento anterior). Pero un primo divide a otro si y solo si son el mismo. Entonces cada p_i es alguna q_j, y por un argumento similar cada q_j es una p_i, esto implica que p _i=q_i para cada i.
Falta ver que las potencias son las mismas, pero si por ejemplo a_j < b _j dividimos a ambos lados entre

y del lado derecho nos sobran factores p_j que dividen al lado izquierdo y son iguales a alguna p_k, lo cual es imposible. Una contradicción similar elimina el caso a_j > b_j.
Así podemos concluir que las factorizaciones son las mismas.
Ahora, retomemos el problema de expresar el máximo común divisor de dos números como combinación lineal de los mismos. Probamos que siempre es posible escribir (a,b) en la forma au + bv donde u y v son enteros y hemos usado este hecho en diversas pruebas, aunque no mencionamos de manera explícita como hallar esos números. El procedimiento para hallar los coeficientes a y b se basa en el algoritmo de la división y más que escribir explícitamente el proceso, lo ilustraremos con un ejemplo.
Así, deseamos expresas (124,44) como combinación lineal de 124 y 44.
124 = 44 × 2 +36
44 = 36 × 1 + 8
36 = 8 ×4 +4
8 = 4 × 2 +0
Entonces (124,44) =4. Despejamos el 4 y empezamos a sustituir de la siguiente manera:
4 = 36 -(4×8)
=36-4(44-36)
=5 × 36 – (4 ×44)
=5 (124- )44×2)) –( 4 × 44)
= (5 ×124) – 14 ×44
Así, 4 = (124 × 5) –(44 ×14). Comparemos esto con el proceso para calcular únicamente (124,44)(versión rápida):
(124,44)=(44,36)= (36,8)=(8,4)=(4,0)=4
y notemos que los números que aparecen son los mismos que aparecen al desarrollar todo el algoritmo de la división, con lo que comprobamos que el algoritmo de Euclides es en realidad la aplicación sucesiva del algoritmo de la división.
Vale la pena recalcar que los coeficientes que se encuentran no son los únicos, de hecho hay una infinidad de soluciones. Para este caso en particular notamos que:

Cada entero t nos genera una combinación distinta.