$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 整除。