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

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

Si multiplico $2a-1$ por $2a$ y le resto el resultado a $4a^2+1$ se obtiene $4a^2+1-4a^2+2a=2a+1.$ De aquí que el MCD buscado divide a $2a+1$ y a $2a-1.$ Y de nuevo aplico la propiedad: $2a+1-2a+1=2$. De aquí que el MCD buscado divide a $2$ y a $2a-1.$ Pero entonces el MCD$(4a^2+1, 2a-1)=1$ --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 $2^{2008}$ en la división entre 9. Pero el 2008 sigue siendo muy grande... Lo que se hace en estos casos es buscar un exponente $z$ del 2 de manera que el residuo de $2^z$ sea 1 o -1 en la división entre 9. Con el 3 se puede ($2^3=8=-1$ mod 9), pero consideremos el 6: $2^6=1$(mod 9). Ahora lo que se tiene que hacer es dividir el exponente 2008 entre 6: $2008=6(334)+4.$

De aquí que $2^{2008}=2^{6\cdot{334}+4}=16\cdot 2^{6\cdot{334}}=16$(mod 9). De aquí que la respuesta sea: $2009^{2008}$ deja 7 de residuo en la división entre 9.