2021の2021乗を2020で割った余り
西暦の西暦乗の割り算問題です。
西暦n年として、まずは2021を例題で考えます。
最後に、一般化してnのまま解く方法を説明します。
例題：2021年問題
(1) \(2021^{2021}\) を \(2020\) で割った余りは \(1\)
(2) \(2021^{2021}\) を \(2020^2\) で割った余りは \(2021\)
方針
2021と2020の差が1であることに注目して、二項定理を用います。
(2020+1)の2021乗を二項展開すると、ほとんどの項が2020の倍数になります。
(1)は合同式を利用すると楽です。（別解）
解答
\((2021)^{2021}\)
\(=(2020+1)^{2021}\)
\(\displaystyle=\sum_{k=0}^{2021}{}_{2021} {\rm{C}} _k \,2020^{k}\) (∵二項定理)
\(={}_{2021} \rm{C} _0\,2020^0 +\underbrace{ {}_{2021} {\rm{C}} _1 2020^1+\cdots+{}_{2021} {\rm{C}} _{2021}2020^{2021}}_{2020\textbf{の倍数}}\)
\(=1+(2020\textbf{の倍数})\)
よって, \(2021^{2021}\) を \(2020\) で割った余りは \(\color{red}{1}\)
(1)別解：合同式の利用
\(2021\equiv 1\,\pmod{2020}\)
\(2021^{2021}\equiv 1^{2021}\equiv 1\)
よって, \(2021^{2021}\) を \(2020\) で割った余りは \(\color{red}{1}\)
(2)
\((2021)^{2021}\)
\(=(2020+1)^{2021}\)
\(\displaystyle=\sum_{k=0}^{2021}{}_{2021} {\rm{C}} _k \,2020^{k}\) (∵二項定理)
\(={}_{2021} \rm{C} _0\,2020^0 +{}_{2021} \rm{C} _1\,2020^1 +\underbrace{{}_{2021} \rm{C} _2\,2020^2+\cdots}_{2020^2 \textbf{の倍数}}\)
\(=1+2021\cdot 2020 +(2020^2 \textbf{の倍数})\)
\(=1+(1+2020)\cdot 2020 +(2020^2 \textbf{の倍数})\)
\(=1+2020+2020^2+(2020^2 \textbf{の倍数})\)
よって, \(2021^{2021}\) を \(2020^2\) で割った余りは \(\color{red}{2021}\)
一般化～西暦何年でも解けるように～
nを2以上の整数とすると、以下が成り立つ。
(3) \((n+1)^{n+1}\) を \(n\) で割った余りは \(1\)
(4) \((n+1)^{n+1}\) を \(n^2\) で割った余りは \(n+1\)
解説
\((n+1)^{n+1}\)
\(\displaystyle=\sum_{k=0}^{n+1}{}_{n+1} {\rm{C}} _k\,n^k\)
\(=1+(n\textbf{の倍数})\)
∴ \(n\) で割った余りは1
(4)
\((n+1)^{n+1}\)
\(\displaystyle=\sum_{k=0}^{n+1}{}_{n+1} {\rm{C}} _k\,n^k\)
\(=1+{}_{n+1} {\rm{C}} _1\,n+(n^2\textbf{の倍数})\)
\(=1+(n+1)n+(n^2\textbf{の倍数})\)
\(=1+n+n^2+(n^2\textbf{の倍数})\)
∴ \(n^2\) で割った余りは \(n+1\)