$ 2001^{2001} + 2003^{2003} $ 被 4004 整除

求證：$ 2001^{2001} + 2003^{2003} $ 能被 4004 整除。

【等冪和差展開解法】

考慮 $2001^{2001}+1$ 和 $2003^{2003}-1$ 兩數

\[2001^{2001}+1=2001^{2001}+1^{2001}\] \[=\left (2001+1\right )\left (2001^{2000}-2001^{1999}+2001^{1998}-...-2001+1\right)\] 其中 $\left (2001^{2000}-2001^{1999}+2001^{1998}-...-2001+1\right)$ 為奇數，因為
(奇數 - 奇數 + 奇數 - ... - 奇數 + 1) 前面共有 $2000-1+1=2000$ 共偶數個奇數，故存在 $a \in\mathbb{Z}$ 使得 \[2001^{2001}+1=\left (2001+1\right )\left (2a+1\right )\]

同理，考慮 \[2003^{2003}-1=2003^{2003}-1^{2003}\] \[=\left (2003-1\right )\left (2003^{2002}+2003^{2001}+2003^{2000}+...+2003+1\right )\] 其中 $\left (2003^{2002}+2003^{2001}+2003^{2000}+...+2003+1\right )$ 為奇數，因為
(奇數 + 奇數 + 奇數 + ... + 奇數 + 1) 前面共有 $2002-1+1=2002$ 共偶數個奇數，故存在 $b \in\mathbb{Z}$ 使得 \[2003^{2003}-1=\left (2003-1\right )\left (2b+1\right )\] 將以上兩數相加得 \[2001^{2001}+1+2003^{2003}-1\] \[=\left (2001+1\right )\left (2a+1\right )+\left (2003-1)\right )\left (2b+1\right )\] \[=2002\left (2a+2b+2\right )\] \[=4004\left (a+b+1\right )\]

\[\Rightarrow 2001^{2001}+2003^{2003}=4004 k, k\in\mathbb{Z}\] 得證此數被 4004 整除

【同餘 mod 解法】

由於 $4004=4\times 1001$，考慮 4 和 1001 兩數。

Case 4:

$\because 2001\div 4=500 ...1$ 與 $2003\div 4 = 500 ... 3$
$\therefore 2001\equiv 1 (mod\,4)$ 與 $2003\equiv 3\equiv (-1) (mod\,4)$ \[\Rightarrow 2001^{2001}+2003^{2003}\equiv 1^{2001}+(-1)^{2003}\equiv 0 (mod\,4)\] 得此數被 4 整除。

Case 1001:

$\because 2001\div 1001=1 ...1000$ 與 $2003\div 1001 = 2 ... 1$
$\therefore 2001\equiv 1000\equiv (-1) (mod\,1001)$ 與 $2003\equiv 1 (mod\,1001)$ \[\Rightarrow 2001^{2001}+2003^{2003}\equiv (-1)^{2001}+1^{2003}\equiv 0 (mod\,1001)\] 得此數被 1001 整除。

同時被 4 和 1001 整除，又 4 與 1001 互質 $(4, 1001)=1$，

得證 $2001^{2001} + 2003^{2003}$ 被 4004 整除。