(2 por 1): Dos trucos, dos problemas --de divisibilidad

a) Como se sabe, el MCD de dos números divide también a cualquier combinación lineal de los números: puesto que divide a ambos también divide a cualquier expresión de la forma , con enteros. Esta propiedad se usará para reducir los dos números a otros dos, donde el resultado sea obvio.

Si multiplico por y le resto el resultado a se obtiene De aquí que el MCD buscado divide a y a Y de nuevo aplico la propiedad: . De aquí que el MCD buscado divide a y a Pero entonces el MCD --pues divide a 2 y a un impar.

b) El método consiste en reducir la expresión (módulo 9) hasta llegar a una donde el resultado se haga obvio.

Puesto que 2009 pertenece la clase residual del 2 (módulo 9) el problema es equivalente a calcular el residuo de en la división entre 9. Pero el 2008 sigue siendo muy grande... Lo que se hace en estos casos es buscar un exponente del 2 de manera que el residuo de sea 1 o -1 en la división entre 9. Con el 3 se puede ( mod 9), pero consideremos el 6: (mod 9). Ahora lo que se tiene que hacer es dividir el exponente 2008 entre 6:

De aquí que (mod 9). De aquí que la respuesta sea: deja 7 de residuo en la división entre 9.