階乗の和を12で割った余り(数列の和と合同)

方針

解答

⓪ 発想 — どう考え始めるか。 $100$ 個の階乗を全部足して $12$ で割るのは不可能。だが「$12$ で割った余り」だけなら、$12$ の倍数になる項は無視してよい。

$4!=24=12\times 2$ で、$5!,6!,\dots$ はさらに $4!$ を因数に含むから、すべて $12$ の倍数。

つまり余りを決めるのは最初の3項 $1!+2!+3!=9$ だけ。「いつから $12$ の倍数になるか」を見極めるのが急所だ。

① $12$ の倍数になる項を除く。 $k\ge 4$ では $k!\equiv 0(\mathrm{mod}12)$。したがって $$\sum _{k=1}^{100}k!\equiv \sum _{k=1}^{3}k!(\mathrm{mod}12).$$ ② 残りを計算する。 $1!+2!+3!=1+2+6=9$。

③ 余りを求める。 $9<12$ だから $$\sum _{k=1}^{100}k!\equiv 9(\mathrm{mod}12).$$ 求める余りは $9$。

まとめ 和の余りは、合同でみると“大きい階乗はすべて $0$”で消え、$1!+2!+3!=9$ だけが残る。数列の和と整数(合同)の融合で、$100$ 項の計算が $3$ 項に縮む。答えは $9$。

発展 — 一歩先へ。 法を $100$ にすると、$10!$ 以降が $100$ の倍数(因数 $2,5$ が十分)だから、$\sum _{k=1}^{100}k!\equiv \sum _{k=1}^{9}k!\equiv 13(\mathrm{mod}100)$、つまり下2桁は $13$。「ある項から先が法の倍数」という構造は、階乗が絡む合同式で繰り返し使える強力な観察だ。

別解

別解 — 「いつ $12$ の倍数になるか」を素因数で押さえる(苦手な人向け)。 $12=2^2\times 3$。ある階乗が $12$ の倍数になるには、因数に $2$ が2個と $3$ が1個あればよい。

$k!$ を順に見る。$3!=6$ は $2$ が1個で足りない。$4!=24=2^3\times 3$ で初めて条件を満たす。以降の $5!,6!,\dots$ は $4!$ を丸ごと含むから、みな $12$ の倍数。

だから $\sum _{k=1}^{100}k!$ を $12$ で割った余りは、$k=1,2,3$ の分だけで決まる。

$$1!+2!+3!=1+2+6=9.$$

$4!$ 以降は「余りに何も足さない」。$100$ 項の巨大な和が、たった3項の足し算に潰れる — 合同式の威力である。