Find the greatest common divisor of $2003^4 + 1$ and $2003^3 + 1$ Find the greatest common divisor of $2003^4 + 1$ and $2003^3 + 1$ without the use of a calculator. It is clear that $2003^4+1$ has a $082$ at the end of its number so $2003^4+1$ only has one factor of 2, while $2003^3+1$ has a $028$ at the end of its number so  $2003^3+1$ has 2 factors of 2. The answer is supposed to be 2, but at this point it could be greater than 2. Any ideas? This was on a previous qualifying exam at BU.

Let $d=\text{ GCD }(2003^3+1,2003^4+1)$, then $d$  divides $2003(2003^3+1)-(2003^4+1)=2003-1=2002=2\cdot 7\cdot 11 \cdot 13$, and since both of $2003^3+1$ and $2003^4+1$ are even we have $d\geq 2$.
Since $2003=2002+1=2\cdot 7\cdot 11 \cdot 13 + 1$ it follows $2003^4+1$ gives residue $2$ when is divided by $7, 11$ or $13$. Then $d|2002$ but $d$ doesn't divide $7,11$ or $13$. It follows $d=2$.
