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)は合同式を利用すると楽です。(別解)


解答

(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\)

解説

(3)

\((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\)