La comunidad de olímpicos, ex-olímpicos, entrenadores y seguidores de la Olimpiada en Chihuahua, wherever they are in the world.
Por supuesto cualquier olímpico mexicano (para que parar ahí, de todo el mundo pues), esta invitado a comentar.
sábado, 10 de julio de 2010
Problema del día.
Demostrar que el máximo común divisor de a²+b²-nab y de a+b también divide a n+2.
***SPOILER*** Sea mcd(a²+b²-nab, a+b) = d entonces d|a+b y d|a²+b²-nab. Entonces d|(a+b)^2 d|a^2+b^2+2ab Como d divide a la diferencia tenemos que: d|(a^2+b^2+2ab)-(a²+b²-nab.) d|ab(n+2)
Entonces si demostramos que mcd(ab,d)=1, acabamos.
Sea mcd(ab,d)=e
e|ab y como e|d, entonces e|a+b e|a^2+b^2+2ab e|a^2+b^2 por otro lado a=-b mod e entonces a^2=b^2 mod e e|a^2-b^2
e|2a^2 e|2b^2 supongamos que e es de la forma e=2^k. Ahora como e|a+b, entonces a+b es par, si a y b son pares entonces dejan de ser primos realtivos, si a y b son impares entonces ab es impar, pero como e|ab y llegamos a un absurdo.
Entonces mcd(e,2)=1 y e|a^2
pero como mcd(a,b)=1 entonces mcd(a^2,b^2)=1 entonces e=1 y mcd(ab,d)=1, que era lo que queriamos demostrar. *** END OF SPOILER ****
Primero una autocorrecion en "supongamos que e es de la forma e=2^k" quize decir supongamos que "e es de la forma e=2^k*b con k>=1 y b impar".
Otra cosa es que ya les habia enseñado a mis alumnos (probablemente los de juarez tambien sepan) lo que quiere decir (a,b)=1.
Y voy a destacar un teorema muy usado en mi demostración para que vallan aprendiendo mas teoremas los novicios. Teorema!! si a|bc y (a,b)=1, entonces a|c.
Aunque muchos sepan que es (a,b) = 1, no hay razón para no escribir "a y b son primos relativos" o "a y b no tienen factores en comun" o "el maximo comun divisor de a y b es 1", cosas que son faciles de googlear en caso de que no sepan que es "primos relativos" o "maximo comun divisor". Sin embargo (a,b) = 1 es mas dificil de saber que es sin saberlo antes.
Buena nota sobre a|bc implica a|c cuando a y b son primos relaticos.
***SPOILER***
ResponderBorrarSea mcd(a²+b²-nab, a+b) = d
entonces d|a+b y d|a²+b²-nab.
Entonces d|(a+b)^2
d|a^2+b^2+2ab
Como d divide a la diferencia tenemos que:
d|(a^2+b^2+2ab)-(a²+b²-nab.)
d|ab(n+2)
Entonces si demostramos que mcd(ab,d)=1, acabamos.
Sea mcd(ab,d)=e
e|ab
y como e|d, entonces e|a+b
e|a^2+b^2+2ab
e|a^2+b^2
por otro lado
a=-b mod e
entonces
a^2=b^2 mod e
e|a^2-b^2
e|2a^2
e|2b^2
supongamos que e es de la forma e=2^k. Ahora como e|a+b, entonces a+b es par, si a y b son pares entonces dejan de ser primos realtivos, si a y b son impares entonces ab es impar, pero como e|ab y llegamos a un absurdo.
Entonces mcd(e,2)=1 y e|a^2
pero como mcd(a,b)=1 entonces mcd(a^2,b^2)=1 entonces e=1 y mcd(ab,d)=1, que era lo que queriamos demostrar.
*** END OF SPOILER ****
Creo que vale la pena explicar que es (a,b) = 1. Nosotros sabemos, pero el blog tambien es para principiantes.
ResponderBorrar(a,b) = 1, significa que el máximo común divisor de a y b es 1. Es decir, a y b no tienen ningún factor en común.
Primero una autocorrecion en "supongamos que e es de la forma e=2^k" quize decir supongamos que "e es de la forma e=2^k*b con k>=1 y b impar".
ResponderBorrarOtra cosa es que ya les habia enseñado a mis alumnos (probablemente los de juarez tambien sepan) lo que quiere decir (a,b)=1.
Y voy a destacar un teorema muy usado en mi demostración para que vallan aprendiendo mas teoremas los novicios.
Teorema!! si a|bc y (a,b)=1, entonces a|c.
Aunque muchos sepan que es (a,b) = 1, no hay razón para no escribir "a y b son primos relativos" o "a y b no tienen factores en comun" o "el maximo comun divisor de a y b es 1", cosas que son faciles de googlear en caso de que no sepan que es "primos relativos" o "maximo comun divisor". Sin embargo (a,b) = 1 es mas dificil de saber que es sin saberlo antes.
ResponderBorrarBuena nota sobre a|bc implica a|c cuando a y b son primos relaticos.
Mi solución es un poco distinta a la tuya Isaí, aquí va:
ResponderBorrarUsó la siguiente observación (que tú también usas):
(m,n) = (m-n, n).
Entonces tenemos:
d = (a^2+b^2-nab , a+b) = (a^2+b^2-nab - (a^2+b^2+2ab), a+b) = (-(n+2)ab,a+b) = ((n+2)ab,a+b).
Ahora (a+b,a) = (b,a) = 1 y (a+b,b) = (a,b) = 1. Por lo tanto (a+b,ab) = 1.
Entonces usando el teorema que mencionas al final tenemos:
d = ((n+2)ab, a+b) = (n+2, a+b). Lo cual demuestra que d|(n+2)