10^10を2020で割った余り / 2020 一橋大学第1問

(1)について
- 解法1：法は 20 と 101
- 解法2：法は 2020
(2)について
- 解法 1：法は 20 と 101
- 解法 2：法は 2020

問題

以下の問いに答えよ。
(1)　 $10^{10}$ を 2020 で割った余りを求めよ。
(2)　100 桁の正の整数で各位の数の和が 2 となるもののうち，2020 で割り切れるものの個数を求めよ。

合同式の法に何を選ぶかがポイントですね。20 と 101 を選ぶ解法と 2020 を選ぶ解法を紹介します。
(1)は 20 と 101 を選ぶ方が自然な感じですが，(2)は 2020 を選ぶ方が楽です。

解説の pdf も作りました。きれいなレイアウトで読みたい方はこちらをどうぞ。

drive.google.com

(1)について

解法1：法は 20 と 101

$2020=2^2\cdot 5\cdot 101=20\cdot 101$ と素因数分解できるので $bmod\, 20$ と $bmod\, 101$ にわけて考えます。

$\bmod\, 20$ で考えると $10^2=100\equiv 0$ より

$10^{10}=(10^2)^5\equiv 0\pmod{20}\mbox{　……(A)}$

$\bmod\, 101$ で考えると $10^2=100\equiv -1$ より $10^4=(10^2)^2\equiv (-1)^2=1$ なので

$10^{10}=(10^4)^2\cdot 10^2\equiv -1\pmod{101}\mbox{　……(B)}$

(A)(B)から $10^{10}=20a=101b-1$ とおけます（ $a$ , $b$ は整数）。これは 1 次不定方程式です。

$101b-20a=1$ と $101\cdot 1-20\cdot 5=1$ を辺ごとに引くと

$101(b-1)-20(a-5)=0$

101 と 20 は互いに素なので $b-1=5k$ , $a-5=101k$ とおけます（ $k$ は整数）。

$10^{10}=20a=20(101k+5)=2020k+100$

求める余りは $\mathbf{100}$ です。

解法2：法は 2020

入試問題である以上，2020 で割った余りの周期はそんなに長くないはずです。
素因数分解せずにはじめから $\bmod\, 2020$ で考えても解けます。

\begin{align*}
10^4 &=2020\cdot 4+1920\equiv 1920\\
10^5 &\equiv 19200=2020\cdot 9+1020\equiv 1020\\
10^6 &\equiv 10200=2020\cdot 5+100\equiv 100\\
10^7 &\equiv 1000=10^3
\end{align*}

$10^7 \equiv 10^3 \pmod{2020}$ から周期は 4 だろうと予想できます。

\begin{align*}
10^{n+4}-10^n &=10^n(10^4-1)=10^n\cdot 9999=10^{n-2}\cdot 999900\\
&=10^{n-2}\cdot 2020\cdot 495\equiv 0\pmod{2020}\quad (n\geqq 2)
\end{align*}

$n\geqq 2$ のとき $10^{n+4}\equiv 10^n\pmod{2020}\mbox{　……(C)}$ です。