数検１級一次過去問（１）

【問題】
$p$ が素数のとき、 $p$ の倍数でない整数 $n$ に対して、 $n^{p-1}-1$ は $p$ で割り切れます。
さて、 $2003$ は素数です。 $2^{2000}$ を $2003$ で割った余りを、上の定理を活用して計算しなさい。

【解答】
上の定理より、 $2^{2002}-1$ は $2003$ で割り切れるので、ある整数 $n$ を使って、
$2^{2002}-1 = 2003n$ 　　・・・(1)
と書ける。
さて、求める余りを $l$ とすると、
$2^{2000}$ ＝ $2003k+l$ 　・・・(2)
(1)と(2)より、
$4(2003k+l)-1 = 2003n$
上式の右辺は $2003$ の倍数だから、左辺の $4l-1$ も $2003$ の倍数である。
$l$ は $2003$ で割ったときの余りだから、 $0$ ≦ $l$ ≦ $2002$ 。
これを満たす $l$ は $4l-1 = 2003$ である。つまり $l = 501$ 。