Find the greatest common divisor of $2003^4 + 1$ and $2003^3 + 1$

Question

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.

Answer 1

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$.

Answer 2

$ d\mid \color{#c00}{a^3}\!+\!1,\color{#0a0}{a^4}\!+\!1\,\Rightarrow {\rm mod}\ d\!:\ \color{#c00}{a^3\equiv \color{}{-1}}\equiv \color{#c00}{a^3}\color{#0a0} a\equiv \color{#c00}-a\,\Rightarrow\,a\equiv 1\,\Rightarrow 1\equiv a^3\equiv \color{#c00}{-1}\,\Rightarrow 2\equiv 0\,\Rightarrow d\mid 2$

Answer 3

$d = \text{gcd}(2003^4+1,2003^3+1) \Rightarrow d \mid 2003^4-2003^3 = 2003^3\cdot 2002 = 2003^3\cdot 2\cdot 7\cdot 11\cdot 13$, and by checking case by case, we have $2$ is the only number such that $d$ divides into evenly. So $d = 2$.