Teoría de números... Algoritmo de Euclides
Agradecería su ayuda porque tengo examen de esto y no entiendo... Por favor colabórenme
1) Pruebe que si de es un divisor común de a y b, entonces de = gcd(a, b) si y solo si gcd(a/d, b/d) = 1.
2) Suponga que gcd(a, b) = 1 y pruebe lo siguiente:
a) gcd(a + b, a ? B) = 1 o 2.
b) gcd(2a + b, a + 2b) = 1 o 3.
c) gcd(a + b, a2 + b2) = 1 o 2.
d) gcd(a + b, a2 ? Ab + b2) = 1 o 3
3) Pruebe que si gcd(a, b) = 1, entonces gcd(a + b, ab) = 1.
4) Sean a y b enteros no todos cero, demuestre que las siguientes condiciones son equivalentes
a) a|b.
b) gcd(a, b) = |a|.
c) lcm(a, b) = |b|.
5) Encuentre al lcm(143, 227), lcm(306, 657) y lcm(272, 1479)
6) Sean a y b enteros no todos cero, demuestre que
a) gcd(a, b) = lcm(a, b) si y solo si a = b.
b) Si que > 0, entonces lcm(ka, kb) = klcm(a, b).
c) Si m es cualquier m´ultiplo com´un de a y b, entonces lcm(a, b)|m.
6) Sean a, b, c enteros, de los cuales dos no son cero, y de = gcd(a, b, c). Pruebe que
d = gcd(gcd(a, b), c) = gcd(a, gcd(b, c))
1) Pruebe que si de es un divisor común de a y b, entonces de = gcd(a, b) si y solo si gcd(a/d, b/d) = 1.
2) Suponga que gcd(a, b) = 1 y pruebe lo siguiente:
a) gcd(a + b, a ? B) = 1 o 2.
b) gcd(2a + b, a + 2b) = 1 o 3.
c) gcd(a + b, a2 + b2) = 1 o 2.
d) gcd(a + b, a2 ? Ab + b2) = 1 o 3
3) Pruebe que si gcd(a, b) = 1, entonces gcd(a + b, ab) = 1.
4) Sean a y b enteros no todos cero, demuestre que las siguientes condiciones son equivalentes
a) a|b.
b) gcd(a, b) = |a|.
c) lcm(a, b) = |b|.
5) Encuentre al lcm(143, 227), lcm(306, 657) y lcm(272, 1479)
6) Sean a y b enteros no todos cero, demuestre que
a) gcd(a, b) = lcm(a, b) si y solo si a = b.
b) Si que > 0, entonces lcm(ka, kb) = klcm(a, b).
c) Si m es cualquier m´ultiplo com´un de a y b, entonces lcm(a, b)|m.
6) Sean a, b, c enteros, de los cuales dos no son cero, y de = gcd(a, b, c). Pruebe que
d = gcd(gcd(a, b), c) = gcd(a, gcd(b, c))
1 Respuesta
Respuesta de Valero Angel Serrano Mercadal
2
Otra vez me salio el signo de interrogación, voy a enviarlo de nuevo a ver...
1) Pruebe que si de es un divisor común de a y b, entonces de = gcd(a, b) si y solo si gcd(a/d, b/d) = 1.
2) Suponga que gcd(a, b) = 1 y pruebe lo siguiente:
a) gcd(a + b, a - b) = 1 o 2 b) gcd(2a + b, a + 2b) = 1 o 3
c) gcd(a + b, a2 + b2) = 1 o 2 d) gcd(a + b, a2 - ab + b2) = 1 o 3
3) Pruebe que si gcd(a, b) = 1, entonces gcd(a + b, ab) = 1
4) Sean a y b enteros no todos cero, demuestre que las siguientes condiciones son equivalentes
a) a|b.
b) gcd(a, b) = |a| c) lcm(a, b) = |b|
5) Encuentre al lcm(143, 227), lcm(306, 657) y lcm(272, 1479)
6) Sean a y b enteros no todos cero, demuestre que
a) gcd(a, b) = lcm(a, b) si y solo si a = b
b) Si que > 0, entonces lcm(ka, kb) = klcm(a, b)
c) Si m es cualquier multiplo comun de a y b, entonces lcm(a, b)|m
7) Sean a, b, c enteros, de los cuales dos no son cero, y de = gcd(a, b, c). Pruebe que
de = gcd(gcd(a, b), c) = gcd(a, gcd(b, c))
---agradezco su colaboración... gracias
1) Pruebe que si de es un divisor común de a y b, entonces de = gcd(a, b) si y solo si gcd(a/d, b/d) = 1.
2) Suponga que gcd(a, b) = 1 y pruebe lo siguiente:
a) gcd(a + b, a - b) = 1 o 2 b) gcd(2a + b, a + 2b) = 1 o 3
c) gcd(a + b, a2 + b2) = 1 o 2 d) gcd(a + b, a2 - ab + b2) = 1 o 3
3) Pruebe que si gcd(a, b) = 1, entonces gcd(a + b, ab) = 1
4) Sean a y b enteros no todos cero, demuestre que las siguientes condiciones son equivalentes
a) a|b.
b) gcd(a, b) = |a| c) lcm(a, b) = |b|
5) Encuentre al lcm(143, 227), lcm(306, 657) y lcm(272, 1479)
6) Sean a y b enteros no todos cero, demuestre que
a) gcd(a, b) = lcm(a, b) si y solo si a = b
b) Si que > 0, entonces lcm(ka, kb) = klcm(a, b)
c) Si m es cualquier multiplo comun de a y b, entonces lcm(a, b)|m
7) Sean a, b, c enteros, de los cuales dos no son cero, y de = gcd(a, b, c). Pruebe que
de = gcd(gcd(a, b), c) = gcd(a, gcd(b, c))
---agradezco su colaboración... gracias
Ahora si intentaré contestar. Recordar que gcd = mcd o MCD (máximo común divisor) en español y lcm = mcm (mínimo común múltiplo) por si alguien no ha caído.
1) Sea de el máximo común divisor de a y b.
Sea d1 = mcd(a/d, b/d) ==>
(a/d)/d1 y (b/d)/d1 serán enteros porque d1 los divide ==>
a/(d·d1) y b/(d·d1) serán enteros ==>
d·d1 es divisor de a y b. Pero como d es el mcd(a,b) ==>
d·d1 no puede ser mayor que d ==>
d1=1
Ahora en el otro sentido. Sea de un divisor de a y b. Hay que probar que si mcd(a/d, b/d) =1 entonces de es el mcd(a, b)
Por ser mcd(a/d, b/d)=1 no tienen ningún divisor común:
a/d = a1
b/d = b1
con a1 y b1 primos entre sí
a = a1·d
b = b1·d
El mcd(a, b) será de y ya vale. Cualquier otro factor extra solo podría estar en a1 o b1, pero no en los dos, ya que a1 y b1 carecen de cualquier divisor común.
-------------------------------------------------------------------------------------------------------------
Para lo que viene a continuación demostraré antes esta igualdad, no sé si ya se da por demostrada pero la demuestro por si acaso.
mcd(a,b) = mcd(a-b,b)
Sea d un divisor de {a, b} siendo a/d=n y b/d=m ==>
(a-b)/d = a/d - b/d = n - m
Luego d divide a (a-b) por demostración y a "b" por hipótesis de partida.
Es decir, divisores de {a, b} incluido en divisores de {(a-b), b}
Y si d es un divisor de {(a-b), b} siendo a/d = n y (a-b)/d = m ==>
a/d = (a-b)/d + b/d = m + n
Luego d divide a "a" por demostración y a "b" por hipótesis de partida.
Es decir, divisores de {(a-b), b} incluidos en divisores de {a, b}
De las dos inclusiones se deduce que divisores de {(a-b), b} = divisores de {a, b} y por lo tanto a los mcd no les quedará más remedio que ser el mismo.
También usare mcd(a,b) = mcd (a, b-a) que se demuestra igual.
2a)
Usando la igualdad recién demostrada:
mcd(a+b,a-b) = mcd(a+b - (a-b), a-b)) = mcd(2b, a-b)
Como mcd(a, b)=1 significa que no hay divisores comunes, es decir si "d" divide a "b" (siendo n = b/d) entonces "d" no divide a "a".
(a-b) / d = a/d - b/d = a/d + n que no es entero porque "d" no dividía a "a". Luedo "d" no divide a (a-b)
Luego lo único de 2b que puede dividir a (a-b) es el 2, limitando a {1, 2} los posibles divisores de {2b, (a-b)}
Y en resumen que mcd(a+b, a-b) = 1 ó 2
Si "a" y "b" son impares será 2 y si uno es par y otro impar será 1.
2b)
mcd(2a+b, a+2b) = mcd(2a+b-a-2b, a+2b) = mcd(a-b, a+2b) =
= mcd(a-b, a+2b-(a-b)) = mcd(a-b,3b)
Y con igual razonamiento que antes se llega a que el mcd es 1 ó 3.
2c)
¡Uy, aquí me huele mal algo! Cuando pones
gcd(a + b, a2 + b2) = 1 o 2
A2 quiere decir "a" al cuadrado y b2 es "b" al cuadrado.
Cuando me lo digas continuaré, que además ya estoy bastante agotado con estos problemas.
1) Sea de el máximo común divisor de a y b.
Sea d1 = mcd(a/d, b/d) ==>
(a/d)/d1 y (b/d)/d1 serán enteros porque d1 los divide ==>
a/(d·d1) y b/(d·d1) serán enteros ==>
d·d1 es divisor de a y b. Pero como d es el mcd(a,b) ==>
d·d1 no puede ser mayor que d ==>
d1=1
Ahora en el otro sentido. Sea de un divisor de a y b. Hay que probar que si mcd(a/d, b/d) =1 entonces de es el mcd(a, b)
Por ser mcd(a/d, b/d)=1 no tienen ningún divisor común:
a/d = a1
b/d = b1
con a1 y b1 primos entre sí
a = a1·d
b = b1·d
El mcd(a, b) será de y ya vale. Cualquier otro factor extra solo podría estar en a1 o b1, pero no en los dos, ya que a1 y b1 carecen de cualquier divisor común.
-------------------------------------------------------------------------------------------------------------
Para lo que viene a continuación demostraré antes esta igualdad, no sé si ya se da por demostrada pero la demuestro por si acaso.
mcd(a,b) = mcd(a-b,b)
Sea d un divisor de {a, b} siendo a/d=n y b/d=m ==>
(a-b)/d = a/d - b/d = n - m
Luego d divide a (a-b) por demostración y a "b" por hipótesis de partida.
Es decir, divisores de {a, b} incluido en divisores de {(a-b), b}
Y si d es un divisor de {(a-b), b} siendo a/d = n y (a-b)/d = m ==>
a/d = (a-b)/d + b/d = m + n
Luego d divide a "a" por demostración y a "b" por hipótesis de partida.
Es decir, divisores de {(a-b), b} incluidos en divisores de {a, b}
De las dos inclusiones se deduce que divisores de {(a-b), b} = divisores de {a, b} y por lo tanto a los mcd no les quedará más remedio que ser el mismo.
También usare mcd(a,b) = mcd (a, b-a) que se demuestra igual.
2a)
Usando la igualdad recién demostrada:
mcd(a+b,a-b) = mcd(a+b - (a-b), a-b)) = mcd(2b, a-b)
Como mcd(a, b)=1 significa que no hay divisores comunes, es decir si "d" divide a "b" (siendo n = b/d) entonces "d" no divide a "a".
(a-b) / d = a/d - b/d = a/d + n que no es entero porque "d" no dividía a "a". Luedo "d" no divide a (a-b)
Luego lo único de 2b que puede dividir a (a-b) es el 2, limitando a {1, 2} los posibles divisores de {2b, (a-b)}
Y en resumen que mcd(a+b, a-b) = 1 ó 2
Si "a" y "b" son impares será 2 y si uno es par y otro impar será 1.
2b)
mcd(2a+b, a+2b) = mcd(2a+b-a-2b, a+2b) = mcd(a-b, a+2b) =
= mcd(a-b, a+2b-(a-b)) = mcd(a-b,3b)
Y con igual razonamiento que antes se llega a que el mcd es 1 ó 3.
2c)
¡Uy, aquí me huele mal algo! Cuando pones
gcd(a + b, a2 + b2) = 1 o 2
A2 quiere decir "a" al cuadrado y b2 es "b" al cuadrado.
Cuando me lo digas continuaré, que además ya estoy bastante agotado con estos problemas.
Exactamente ; a2 quiere decir "a" al cuadrado y b2 es "b" al cuadrado...
Y gracias por ayudarme... enserio que necesito estudiar mucho estos ejercicios... son algo pesaditos para mi... eres un duro de las matemáticas... pero echame otro empujón...
Y gracias por ayudarme... enserio que necesito estudiar mucho estos ejercicios... son algo pesaditos para mi... eres un duro de las matemáticas... pero echame otro empujón...
Vale, lo pondré de manera menos confusa para mí. Aquí se suele utilizar el símbolo ^ para la potencia.
2c) mcd(a + b, a^2 + b^2) = 1 o 2
Supondremos que a<=b. Si no es así, los intercambiamos que la expresión que queda es la misma.
Restaremos "a" veces el término (a+b) al segundo término
mcd(a+b,a^2+b^2) = mcd(a+b, a^2 + b^2 - a(a+b)) =
= mcd(a+b, a^2 + b^2 - a^2 - ab) = mcd(a+b, b^2 - ab) =
= mcd(a+b, b(b-a))
Qué agudos fuimos con imposición inicial para que el segundo término sea positivo.
Sea d un divisor de (a+b) y b(b-a).
Como mcd(a,b)=1 ==> "d" no puede ser un divisor mayor que 1 de "a" porque
(a+b)/ d = a/d +b/d = n + b/d
Con "n" entero y b/d no entero (ya que si lo fuese dividiría a "b" y por tanto el mcd(a, b) sería "d" al menos)
Y no divide a (a-b) luego "d" mayor que 1 que divida a "a" no divide a (a+b)
Análogamente se demuestra que "d" mayor que 1 que divida a "b" no divide a (a+b).
Como "d" no divide a "b", para que pueda dividir a b(b-a) los factores primos de "d" no simplificables con "b" deben dividir a (b-a). Y además deben existir esos factores, no pueden ser el 1 a secas.
En el ejercio 2a) teniamos demostrado que mcd(a+b, a-b) = 1 ó 2 si mcd(a+b)=1
o lo que es lo mismo para nuestro caso que mcd(a+b, b-a) = 1 o 2 si mcd(a+b)=1
Entonces esos factores primos propios de (b-a) contenidos en "d", como también dividen a (a+b), solo pueden ser 1 o 2.
Recapitulemos.
1) "d" Puede ser 1, siempre es posible, nadie se lo impide.
2) "d" No puede ser divisor de "b" multiplicado por 1 porque no dividiría a (a+b)
3) ¿"d" Podría ser un divisor de "b" (llamémosle "c") multiplicado por 2 de forma que "d" ya no fuera divisor de "b"? Ahora veremos hasta que punto.
"d" también debe dividir a (a+b)
Sea n=b/c.
(a+b)/d = (a+b)/(2c) = (a+cn)/(2c) = m con "m" entero. ==>
a+cn=2cm ==> a=c(2m-n) ==>a/c=2m-n
Entonces c también divide a "a", es por lo tanto divisor de "a" y "b", pero como mcd(a,b)=1 ==> c= 1 ==> d = 2
Luego un divisor "d" de (a+b) y b(b-a) es 1 o 2 y su mcd será 1 o 2 y el mcd de la expresión inicial será 1 o 2.
¡Cuatro horas para esto!
2d) mcd(a + b, a^2 - ab + b^2) = 1 o 3
De nuevo otra expresión donde se pueden intercambiar "a" y "b", para no meternos en líos y discusiones bizantinas de si el mcd está definido para naturales o para enteros y si los teoremas usados funcionan con negativos, hagamos que sea a>=b.
Restamos (a-b) veces (a+b) al segundo término
mcd(a+b, a^2-ab+b^2) = mcd (a+b, a^2 - ab + b^2 + a^2 - b^2)=
= mcd(a+b, 2a^2 - ab) = mcd(a+b, a(2a-b))
Con idéntica demostración a la del ejercicio anterior. Por ser mcd(a, b)=1 los divisores "d" mayores que 1 de ambos términos no pueden ser divisores de a o b.
Como "d" no divide a "a", para que pueda dividir a a(2a-b) los factores primos de "d" no simplificables con "a" deben dividir a (2a-b). Y además deben existir esos factores, no pueden ser el 1 a secas.
Entre medias veamos cuanto vale un mcd. Recordemos que hemos usado hasta la saciedad el restar un término al otro... ¡Pero también se puede sumar!
mcd(a+b, 2a-b) = mcd(a+b, 3a)
En 2b) teníamos algo de este estilo que te djo que demuestres que vale 1 ó 3
Los factores propios de (2a-b) presentes en "d" valdrán 3. Es decir d=3c con "c" divisor de "a"
"d" también debe dividir a (a+b)
Sea n=a/c.
(a+b)/d = (a+b)/(3c) = (cn+b)/(3c) = m con "m" entero. ==>
b+cn=3cm ==> b=c(3m-n) ==>b/c=3m-n
Entonces "c" también divide a "b", es por lo tanto divisor de "a" y "b", pero como mcd(a,b)=1 ==> c= 1 ==> d = 3
Luego un divisor "d" de (a+b) y a(2a-b) es 1 o 3 y su mcd será 1 o 3 y el mcd de la expresión inicial será 1 o 3.
/-----------------------------------------------------------/
3) Pruebe que si gcd(a, b) = 1, entonces gcd(a + b, ab) = 1
Como ya hemos visto varias veces, si mcd(a,b)=1 ==> los divisores de (a+b) mayores que 1 no pueden ser ni divisores de "a" ni de "b".
Sea "d" divisor de (a+b) y ab. Como de no puede dividir a "a" aquellos factores primos de "d" que no puedan simplificarse con "a" tendrán que estar en el descomposición de "b". Esos factores dividirán a "b", pero también a a+b
pero mcd(b, a+b) = mcd(b, a) = 1
Luego esos factores son 1 con lo cual "d" simplificará (dividirá) a "a" y entraremos en contradicción con lo dicho arriba salvo que de =1.
Luego mcd(a+b, ab)=1
/---------------------------------------------------------------/
Sean a y b enteros no todos cero, demuestre que las siguientes condiciones son equivalentes:
a) a|b.
b) gcd(a, b) = |a|
c) mcm(a, b) = |b|
Si a|b entonces restamos a "b" b/a veces "a" y queda
mcd(a, b) = mcd(a, b-(b/a)a) = mcd(a,0) =a
Si mcd(a,b)=|a| a|b porque un mcd es un divisor de ambos números
luego proposiciones a) y b) son equibvalentes
Si a|b ==> "b" es un múltiplo de "a". Y "b" también es multiplo "b" y es el mínimo múltiplo posible de ambos.
Si |b| es el mcm(a, b) todos los factores primos de "a" no aportaron nada al calcular el mcm porque estaban contenidos en "b" con menor o igual exponente. Y por tanto en el cociente b/a podremos tachar todos los factores del denominador y quedará un número entero con lo cual a|b
con esto 3) es equivalente a 1)
Y 2) equivalente a 3) por propiedad transitiva.
/------------------------------------------------------------/
5) Encuentre al lcm(143, 227), lcm(306, 657) y lcm(272, 1479)
¡Vamos, que no me digas que no sabes hacer esto!
Me salgo por la tangente y lo haré calculando el mcd que es mejor para mí
227-143=84
143-84=59
84-59=25
59-25=24
25-24=1
como el mcd=1 el mcm(227,143) = 227 x 143 = 32461
--------------------------
306 = 2 X 3^2 x 17
657 = 3^2 x 73
mcm(306, 657) = 2 x 3^2 x 17 x 73 = 22338
-------------------------
272 = 2^4 x 17
No es necesario descomponer 1479, simplemente veamos si es divisible por los factores primos de 272 que son el 2 y el 17. por 2 ya se ve que no
1479 = 17 x 87
mcm(272, 1479) = 2^4 x 17 x 87 = 23664
/---------------------------------------------------------/
6) Sean a y b enteros no todos cero, demuestre que
a) mcd(a, b) = mcm(a, b) si y solo si a = b
b) Si que > 0, entonces mcm(ka, kb) = k·mcm(a, b)
c) Si m es cualquier multiplo comun de a y b, entonces lcm(a, b)|m
a)
El mcd de dos números siempre es menor que el menor de ellos
El mcm siempre es mayor que el mayor de ellos
Supongamos a <= b
mcd(a,b) <= a <= b <= mcm(a,b)
Si los extremos son iguales también lo es lo interior y a=b
Y si a=b en efecto severifica mcd(a, b) = mcm(a, b), se demuestra casi por simple definición.
b)
Si m=mcm(a,b)
"a" divide a "m" y "b" divide a "m"
Entonces ak divide a mk y bk divide a mk
Supongamos existe n < mk múltiplo de ak y bk
n=aki=bkj
n/k=ai=bj luego n/k es múltiplo común de "a" y "b"
y como n < mk ==> n/k<m
Pero esto es contradictorio porque n/k es múltiplo de "a" y "b" y menor que m que es su mcm luego m no era el mcm.
Luego mk es el mcm
c)
Si m es cualquier multiplo comun de a y b, entonces mcm(a, b)|m
Sea m múltiplo de "a" y "b"
m = ai = bj
Lo dejo por hoy, ya no me da para más.
2c) mcd(a + b, a^2 + b^2) = 1 o 2
Supondremos que a<=b. Si no es así, los intercambiamos que la expresión que queda es la misma.
Restaremos "a" veces el término (a+b) al segundo término
mcd(a+b,a^2+b^2) = mcd(a+b, a^2 + b^2 - a(a+b)) =
= mcd(a+b, a^2 + b^2 - a^2 - ab) = mcd(a+b, b^2 - ab) =
= mcd(a+b, b(b-a))
Qué agudos fuimos con imposición inicial para que el segundo término sea positivo.
Sea d un divisor de (a+b) y b(b-a).
Como mcd(a,b)=1 ==> "d" no puede ser un divisor mayor que 1 de "a" porque
(a+b)/ d = a/d +b/d = n + b/d
Con "n" entero y b/d no entero (ya que si lo fuese dividiría a "b" y por tanto el mcd(a, b) sería "d" al menos)
Y no divide a (a-b) luego "d" mayor que 1 que divida a "a" no divide a (a+b)
Análogamente se demuestra que "d" mayor que 1 que divida a "b" no divide a (a+b).
Como "d" no divide a "b", para que pueda dividir a b(b-a) los factores primos de "d" no simplificables con "b" deben dividir a (b-a). Y además deben existir esos factores, no pueden ser el 1 a secas.
En el ejercio 2a) teniamos demostrado que mcd(a+b, a-b) = 1 ó 2 si mcd(a+b)=1
o lo que es lo mismo para nuestro caso que mcd(a+b, b-a) = 1 o 2 si mcd(a+b)=1
Entonces esos factores primos propios de (b-a) contenidos en "d", como también dividen a (a+b), solo pueden ser 1 o 2.
Recapitulemos.
1) "d" Puede ser 1, siempre es posible, nadie se lo impide.
2) "d" No puede ser divisor de "b" multiplicado por 1 porque no dividiría a (a+b)
3) ¿"d" Podría ser un divisor de "b" (llamémosle "c") multiplicado por 2 de forma que "d" ya no fuera divisor de "b"? Ahora veremos hasta que punto.
"d" también debe dividir a (a+b)
Sea n=b/c.
(a+b)/d = (a+b)/(2c) = (a+cn)/(2c) = m con "m" entero. ==>
a+cn=2cm ==> a=c(2m-n) ==>a/c=2m-n
Entonces c también divide a "a", es por lo tanto divisor de "a" y "b", pero como mcd(a,b)=1 ==> c= 1 ==> d = 2
Luego un divisor "d" de (a+b) y b(b-a) es 1 o 2 y su mcd será 1 o 2 y el mcd de la expresión inicial será 1 o 2.
¡Cuatro horas para esto!
2d) mcd(a + b, a^2 - ab + b^2) = 1 o 3
De nuevo otra expresión donde se pueden intercambiar "a" y "b", para no meternos en líos y discusiones bizantinas de si el mcd está definido para naturales o para enteros y si los teoremas usados funcionan con negativos, hagamos que sea a>=b.
Restamos (a-b) veces (a+b) al segundo término
mcd(a+b, a^2-ab+b^2) = mcd (a+b, a^2 - ab + b^2 + a^2 - b^2)=
= mcd(a+b, 2a^2 - ab) = mcd(a+b, a(2a-b))
Con idéntica demostración a la del ejercicio anterior. Por ser mcd(a, b)=1 los divisores "d" mayores que 1 de ambos términos no pueden ser divisores de a o b.
Como "d" no divide a "a", para que pueda dividir a a(2a-b) los factores primos de "d" no simplificables con "a" deben dividir a (2a-b). Y además deben existir esos factores, no pueden ser el 1 a secas.
Entre medias veamos cuanto vale un mcd. Recordemos que hemos usado hasta la saciedad el restar un término al otro... ¡Pero también se puede sumar!
mcd(a+b, 2a-b) = mcd(a+b, 3a)
En 2b) teníamos algo de este estilo que te djo que demuestres que vale 1 ó 3
Los factores propios de (2a-b) presentes en "d" valdrán 3. Es decir d=3c con "c" divisor de "a"
"d" también debe dividir a (a+b)
Sea n=a/c.
(a+b)/d = (a+b)/(3c) = (cn+b)/(3c) = m con "m" entero. ==>
b+cn=3cm ==> b=c(3m-n) ==>b/c=3m-n
Entonces "c" también divide a "b", es por lo tanto divisor de "a" y "b", pero como mcd(a,b)=1 ==> c= 1 ==> d = 3
Luego un divisor "d" de (a+b) y a(2a-b) es 1 o 3 y su mcd será 1 o 3 y el mcd de la expresión inicial será 1 o 3.
/-----------------------------------------------------------/
3) Pruebe que si gcd(a, b) = 1, entonces gcd(a + b, ab) = 1
Como ya hemos visto varias veces, si mcd(a,b)=1 ==> los divisores de (a+b) mayores que 1 no pueden ser ni divisores de "a" ni de "b".
Sea "d" divisor de (a+b) y ab. Como de no puede dividir a "a" aquellos factores primos de "d" que no puedan simplificarse con "a" tendrán que estar en el descomposición de "b". Esos factores dividirán a "b", pero también a a+b
pero mcd(b, a+b) = mcd(b, a) = 1
Luego esos factores son 1 con lo cual "d" simplificará (dividirá) a "a" y entraremos en contradicción con lo dicho arriba salvo que de =1.
Luego mcd(a+b, ab)=1
/---------------------------------------------------------------/
Sean a y b enteros no todos cero, demuestre que las siguientes condiciones son equivalentes:
a) a|b.
b) gcd(a, b) = |a|
c) mcm(a, b) = |b|
Si a|b entonces restamos a "b" b/a veces "a" y queda
mcd(a, b) = mcd(a, b-(b/a)a) = mcd(a,0) =a
Si mcd(a,b)=|a| a|b porque un mcd es un divisor de ambos números
luego proposiciones a) y b) son equibvalentes
Si a|b ==> "b" es un múltiplo de "a". Y "b" también es multiplo "b" y es el mínimo múltiplo posible de ambos.
Si |b| es el mcm(a, b) todos los factores primos de "a" no aportaron nada al calcular el mcm porque estaban contenidos en "b" con menor o igual exponente. Y por tanto en el cociente b/a podremos tachar todos los factores del denominador y quedará un número entero con lo cual a|b
con esto 3) es equivalente a 1)
Y 2) equivalente a 3) por propiedad transitiva.
/------------------------------------------------------------/
5) Encuentre al lcm(143, 227), lcm(306, 657) y lcm(272, 1479)
¡Vamos, que no me digas que no sabes hacer esto!
Me salgo por la tangente y lo haré calculando el mcd que es mejor para mí
227-143=84
143-84=59
84-59=25
59-25=24
25-24=1
como el mcd=1 el mcm(227,143) = 227 x 143 = 32461
--------------------------
306 = 2 X 3^2 x 17
657 = 3^2 x 73
mcm(306, 657) = 2 x 3^2 x 17 x 73 = 22338
-------------------------
272 = 2^4 x 17
No es necesario descomponer 1479, simplemente veamos si es divisible por los factores primos de 272 que son el 2 y el 17. por 2 ya se ve que no
1479 = 17 x 87
mcm(272, 1479) = 2^4 x 17 x 87 = 23664
/---------------------------------------------------------/
6) Sean a y b enteros no todos cero, demuestre que
a) mcd(a, b) = mcm(a, b) si y solo si a = b
b) Si que > 0, entonces mcm(ka, kb) = k·mcm(a, b)
c) Si m es cualquier multiplo comun de a y b, entonces lcm(a, b)|m
a)
El mcd de dos números siempre es menor que el menor de ellos
El mcm siempre es mayor que el mayor de ellos
Supongamos a <= b
mcd(a,b) <= a <= b <= mcm(a,b)
Si los extremos son iguales también lo es lo interior y a=b
Y si a=b en efecto severifica mcd(a, b) = mcm(a, b), se demuestra casi por simple definición.
b)
Si m=mcm(a,b)
"a" divide a "m" y "b" divide a "m"
Entonces ak divide a mk y bk divide a mk
Supongamos existe n < mk múltiplo de ak y bk
n=aki=bkj
n/k=ai=bj luego n/k es múltiplo común de "a" y "b"
y como n < mk ==> n/k<m
Pero esto es contradictorio porque n/k es múltiplo de "a" y "b" y menor que m que es su mcm luego m no era el mcm.
Luego mk es el mcm
c)
Si m es cualquier multiplo comun de a y b, entonces mcm(a, b)|m
Sea m múltiplo de "a" y "b"
m = ai = bj
Lo dejo por hoy, ya no me da para más.
Si m es múltiplo de "a" y "b" la descomposición de m en factores primos contendrá todos los factores primos de "a" con su exponente, igualmente tendrá todos los de "b" con su exponente. Es decir, al menos tendrá los no comunes con su exponente y los comunes con el máximo exponente. Eso es precisamente el mcm(a, b), luego m sera el mcm(a, b) multiplicado por algo.
/------------------------------------------------------------------------/
7) Sean a, b, c enteros , de los cuales dos no son cero, y d = gcd(a, b, c).
Pruebe que d = gcd(gcd(a, b), c) = gcd(a, gcd(b, c))
Demostremos primero que si "f" es divisor de "a" y "b" entonces "f" también divide al mcd(a, b)
Tomamos la descomposición de f en factores primos. "f" Deberá factores primos de "a" sin superar el exponente que tienen en "a". Asimismo, estos factores también deberán serlo de "b" y sin superar su exponente. El mcd(a, b) con tiene los factores comunes con el mínimo exponente, "f" tendá eso o menos luego dividirá al mcd.
Por lo tanto los divisores de "a" y "b" serán los mismos que los de mcd(a, b)
Y los divisres de {a, b, c} son los mismos que los de {mcd(a, b), c} y por tanto el mcd es el mismo.
Análogamente se demuestra que mcd(a, b, c)=mcd(a, mcd(b, c))
Bueno, eso es todo. Espero que te haya servido y lo hallas entendido. No olvides puntuar y cerrar la pregunta. No volveré a contestar preguntas que son 10 o 20 preguntas a la vez, se me va la vida en ello. Pregunta solo lo que en verdad no puedas resolver por ti mismo y no sobrecargues las preguntas.
/------------------------------------------------------------------------/
7) Sean a, b, c enteros , de los cuales dos no son cero, y d = gcd(a, b, c).
Pruebe que d = gcd(gcd(a, b), c) = gcd(a, gcd(b, c))
Demostremos primero que si "f" es divisor de "a" y "b" entonces "f" también divide al mcd(a, b)
Tomamos la descomposición de f en factores primos. "f" Deberá factores primos de "a" sin superar el exponente que tienen en "a". Asimismo, estos factores también deberán serlo de "b" y sin superar su exponente. El mcd(a, b) con tiene los factores comunes con el mínimo exponente, "f" tendá eso o menos luego dividirá al mcd.
Por lo tanto los divisores de "a" y "b" serán los mismos que los de mcd(a, b)
Y los divisres de {a, b, c} son los mismos que los de {mcd(a, b), c} y por tanto el mcd es el mismo.
Análogamente se demuestra que mcd(a, b, c)=mcd(a, mcd(b, c))
Bueno, eso es todo. Espero que te haya servido y lo hallas entendido. No olvides puntuar y cerrar la pregunta. No volveré a contestar preguntas que son 10 o 20 preguntas a la vez, se me va la vida en ello. Pregunta solo lo que en verdad no puedas resolver por ti mismo y no sobrecargues las preguntas.
