Dudas de ejercicios matematica discreta

Hace mucho que no me hacen hacer cosas de estas, así que quizá la lió en algún sitio.

1. gcd(18, 20, 45) = 1, así que si planteas 18a + 20b + 45c = 1 obtendrás una solución con a,b,c enteros. Interpreta los coeficientes negativos como el cambio que te devuelven.

2. ni idea, se supone que p es primo? en caso de ser compuesto o 1 el enunciado de 2 es falso. Parecen propiedades de primos de Mersenne, yo miraría por ahí. Nunca se me dieron bien esa clase de problemas xD

3. Lo mismo, ni idea.

4. a Como d divide a a y b, entonces podemos reescribir a = dx y b = dy. Reescribimos la ecuación inicial y tenemos que dx = dyq + r, reordenamos y obtenemos d(x - yq) = r y, finalmente x - yq = r/d. Sabemos que x - yq es un entero, así que d ha de dividir a r para que esto se pueda cumplir. Con esto probamos un sentido de la implicación (si d divide a a y b, entonces divide a b y r). Para el otro sentido hacemos lo mismo : b = dx y r = dy, así que a = d(xq + y) y xq + y = a/d. Podemos aplicar el mismo razonamiento. Para el apartado b, como sabemos que un cierto d divide a a y b si y solo si tambien divide a b y r, también lo hará su máximo común divisor.

5. Supongamos que existen enteros s y t tales que as+bt=1 pero que gcd(a,b) = d, con d!=1. Entonces a = dx, y b = dy, así que si reescribimos obtenemos dxs + dyt = 1, que se puede poner como d(xs + yt) = 1. La parte izquierda siempre será un múltiplo de d, y al tener d>1 podemos garantizar que nunca será 1. Si nos fijamos, x e y son coprimos (ya que es la parte no "englobable" en el máximo común divisor), así que si sustituimos d=1 obtenemos 1(xs + yt) = 1, con x e y coprimos. Por tanto, de existir esos s y t, podemos garantizar que a y b seran coprimos.

6. Esto puedes probarlo como los anteriores, pero tambien puedes usar la propiedad gcd(a,b) = gcd(b, a mod b) (lo que usa el algoritmo de Euclides, vaya).
   gcd(b, a+bk) = gcd(a+bk, b mod (a+bk)) = gcd(a+bk, b) = gcd(b, a+bk mod b) = gcd(b,a mod b) = gcd(a,b).
   De hecho, con esto pruebas algo mas general, y es que gcd(b, a+bk) = gcd(a,b). La propia propiedad es un poco tediosilla de probar, pero es factible (si es que lo necesitas).

7. Esto es similar al anterior.

8. Esto recuerdo que es una propiedad bastante de libro, de hecho creo que si pones ese enunciado en google te lo autocompleta. No me acuerdo de como se demuestra y tampoco quiero pensar mas, la verdad.

#4 No se supone que al encontrar un contraejemplo para un enunciado ya estás probando que es falso de manera satisfactoria?

#8 No entiendo lo que me quieres decir. Qué he hecho mal?

De todas formas, la construcción de un contraejemplo es un método totalmente válido para demostrar que un determinado enunciado es falso. En mi vida me han rechazado nunca una proof de ese tipo. Te refieres a encontrar una familia de enteros que toda ella sirva como contraejemplo para el segundo ejercicio? No entiendo por qué seria necesario. En todo caso lo que he puesto es que lo que se propone en el segundo problema es falso, aunque supongo que hay que asumir que la p es un primo, no lo se. Me parece más interesante demostrar las propiedades de 2) y 3).

#9 #10 pues como dices demuestra primero las propiedades de 2) y 3) y si es verdad que cumplen las propiedades de los primos o el caso que sea, después usas un contraejemplo.
No digo que un contraejemplo no valga pero solo con eso no sirve, luego nos dices como los resolvieron en clase. S2