整数の性質の問題

整数 $a,b,q$ に対して、$a$ と $b$ の最大公約数は $b$ と $a-qb$ の最大公約数に等しい（互除法の原理）。最大公約数を $\gcd (\cdot ,\cdot )$ で表す。

これをくり返し使う。

$(1)$ $5n+3=(3n+1)\cdot 1+(2n+2)$ より
$$\gcd (5n+3,3n+1)=\gcd (3n+1,2n+2)$$

$(2)$ $3n+1=(2n+2)\cdot 1+(n-1)$ より
$$\gcd (3n+1,2n+2)=\gcd (2n+2,n-1)$$

$(3)$ $2n+2=(n-1)\cdot 2+4$ より
$$\gcd (2n+2,n-1)=\gcd (n-1,4)$$

したがって $d_n=\gcd (n-1,4)$ である。$n=1$ のときは $n-1=0$ であり、$\gcd (0,4)=4$ とする（実際、$5\cdot 1+3=8$, $3\cdot 1+1=4$ の最大公約数は $4$ で一致する）。

$4$ の正の約数は $1,2,4$ なので、$n-1$ を $4$ で割った余りで分類する。
- $n-1\equiv 0(\mathrm{mod}4)$ のとき：$d_n=4$
- $n-1\equiv 2(\mathrm{mod}4)$ のとき：$n-1$ は $2$ の倍数だが $4$ の倍数でないので $d_n=2$
- $n-1$ が奇数のとき：$d_n=1$

$n=1,2,\dots ,100$ のとき、$n-1$ は $0,1,2,\dots ,99$ を動く。
- $4$ の倍数：$0,4,8,\dots ,96$ の $25$ 個
- $4$ で割って $2$ 余る数：$2,6,10,\dots ,98$ の $25$ 個
- 奇数：$1,3,5,\dots ,99$ の $50$ 個

よって求める和は
$$4\cdot 25+2\cdot 25+1\cdot 50=100+50+50=200$$

（確認：$n=1$ のとき $8,4$ で最大公約数は $4$。$n=2$ のとき $13,7$ で $1$。$n=3$ のとき $18,10$ で $2$。$n=5$ のとき $28,16$ で $4$。いずれも $\gcd (n-1,4)$ と一致する。）

ユークリッドの互除法より、$\gcd (5n+3,3n+1)=\gcd (3n+1,2n+2)=\gcd (n-1,2n+2)=\gcd (n-1,4)$ となる。したがって $d_n=\gcd (n-1,4)$ である。

$m=n-1$ とおくと $m=0,1,\dots ,99$ である。
- $m=0$ のとき $\gcd (0,4)=4$ より、$d=4$（1個）。
- $m$ が 4 の倍数（$m=4,8,\dots ,96$ の 24個）のとき $d=4$。
- $m$ が偶数で 4 の倍数でないもの（偶数 49個のうち 24個が 4 の倍数なので 25個）のとき $d=2$。
- $m$ が奇数（50個）のとき $d=1$。

和は $4+24\cdot 4+25\cdot 2+50\cdot 1=4+96+50+50=200$。

検算：$n=1$ で $\gcd (8,4)=4$、$n=2$ で $\gcd (13,7)=1$、$n=3$ で $\gcd (18,10)=2$ となり、$\gcd (n-1,4)$ と一致する。