整数論の問題

法が互いに素でないので、素数べきの法に分解する。
- $x\equiv 5(\mathrm{mod}12)$ は $x\equiv 1(\mathrm{mod}4)$ かつ $x\equiv 2(\mathrm{mod}3)$ と同値。
- $x\equiv 11(\mathrm{mod}18)$ は $x\equiv 1(\mathrm{mod}2)$ かつ $x\equiv 2(\mathrm{mod}9)$ と同値。
- $x\equiv 13(\mathrm{mod}20)$ は $x\equiv 1(\mathrm{mod}4)$ かつ $x\equiv 3(\mathrm{mod}5)$ と同値。

法 $2$ と $4$ の条件は $x\equiv 1(\mathrm{mod}4)$ にまとまり、法 $3$ と $9$ の条件は $x\equiv 2(\mathrm{mod}9)$ にまとまる（$2\mathrm{mod}3=2$ で矛盾しない）。よって元の連立合同式は
$$x\equiv 1(\mathrm{mod}4),x\equiv 2(\mathrm{mod}9),x\equiv 3(\mathrm{mod}5)$$
と同値で、中国剰余定理により法 $\mathrm{lcm}(12,18,20)=180$ でただ 1 つの解をもつ。

$x\equiv 2(\mathrm{mod}9)$ を満たす $2,11,20,29,38$ のうち $x\equiv 3(\mathrm{mod}5)$ を満たすのは $38$ なので $x\equiv 38(\mathrm{mod}45)$。$38,83,128,173$ のうち $x\equiv 1(\mathrm{mod}4)$ を満たすのは $173$。よって
$$x\equiv 173(\mathrm{mod}180).$$
検算: $173=12\cdot 14+5=18\cdot 9+11=20\cdot 8+13$。

$1000$ 以下の正の解は $173,353,533,713,893$ の 5 個で、和は
$$5\cdot 173+180\cdot (0+1+2+3+4)=865+1800=2665.$$

まず両立性を確認する。$\gcd (12,18)=6$: $5\equiv 11\equiv 5(\mathrm{mod}6)$ ✓。$\gcd (12,20)=4$: $5\equiv 13\equiv 1(\mathrm{mod}4)$ ✓。$\gcd (18,20)=2$: $11\equiv 13\equiv 1(\mathrm{mod}2)$ ✓。よって解が存在し、法 $\mathrm{lcm}(12,18,20)=180$ で一意に定まる。

解を求める。$x\equiv 13(\mathrm{mod}20)$ より $x=13+20k$。これを $x\equiv 5(\mathrm{mod}12)$ に代入: $13+20k\equiv 1+8k\equiv 5(\mathrm{mod}12)$、$8k\equiv 4(\mathrm{mod}12)$、$2k\equiv 1(\mathrm{mod}3)$、$k\equiv 2(\mathrm{mod}3)$。$k=2+3m$ とおくと $x=53+60m$。
$x\equiv 11(\mathrm{mod}18)$ に代入: $53+60m\equiv 17+6m\equiv 11(\mathrm{mod}18)$、$6m\equiv -6\equiv 12(\mathrm{mod}18)$、$m\equiv 2(\mathrm{mod}3)$。$m=2$ で $x=173$。

確かめ: $173=12\cdot 14+5$ ✓、$173=18\cdot 9+11$ ✓、$173=20\cdot 8+13$ ✓。

よって $x\equiv 173(\mathrm{mod}180)$。$1000$ 以下の正の整数解は $173,353,533,713,893$（次は $1073>1000$）。

和は $173\cdot 5+180(0+1+2+3+4)=865+1800=2665$。