a) Calcular el Máximo Común Divisor (MCD) de $4a^2+1$ y $2a-1$, donde $a$ es un entero positivo cualquiera.
b) Calcular el residuo de $2009^{2008}$ al dividir entre 9.
Para el inciso a) aplica la propiedad siguiente: el MCD debe dividir a cualquier combinación lineal de los números (con los coeficientes de la combinación elegidos adecuadamente). Para el b) reduce la expresión (módulo 9) hasta que el resultado sea obvio.
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.
