整数論の問題

方針 法 $4,5,7$ はどの 2 つも互いに素です。したがって中国剰余定理により、この連立合同式の解は法 $M=4\cdot 5\cdot 7=140$ でただ 1 つに定まり、$x\equiv c(\mathrm{mod}140)$ の形にまとめられます。

手順 1：$M_i=M/m_i$ を求める
$$M_1=\frac{140}{4}=35,M_2=\frac{140}{5}=28,M_3=\frac{140}{7}=20.$$

手順 2：各 $M_i$ の法 $m_i$ での逆元 $y_i$ を求める
- $35\equiv 3(\mathrm{mod}4)$ で、$3\cdot 3=9\equiv 1(\mathrm{mod}4)$ なので $y_1=3$。
- $28\equiv 3(\mathrm{mod}5)$ で、$3\cdot 2=6\equiv 1(\mathrm{mod}5)$ なので $y_2=2$。
- $20\equiv 6(\mathrm{mod}7)$ で、$6\cdot 6=36\equiv 1(\mathrm{mod}7)$ なので $y_3=6$。

手順 3：解を組み立てる
$$x\equiv a_1{M}_1{y}_1+a_2{M}_2{y}_2+a_3{M}_3{y}_3=3\cdot 35\cdot 3+2\cdot 28\cdot 2+4\cdot 20\cdot 6$$
$$=315+112+480=907(\mathrm{mod}140).$$
$907=140\cdot 6+67$ なので
$$x\equiv 67(\mathrm{mod}140).$$

手順 4：確かめ
$67=4\cdot 16+3$、$67=5\cdot 13+2$、$67=7\cdot 9+4$ なので、3 つの合同式をすべてみたします。

解は $x=67+140k$（$k$ は整数）の形で、正の整数のうち最小のものは $k=0$ のときの $x=67$ です。

x≡3 (mod 4), x≡2 (mod 5), x≡4 (mod 7)。4, 5, 7 は互いに素なので、中国剰余定理により mod 140 で一意に定まる。

まず前の 2 式を解く。x=3+4k とおくと 3+4k≡2 (mod 5) より 4k≡-1≡4 (mod 5)。よって k≡1 (mod 5)。したがって x=7+20m、すなわち x≡7 (mod 20)。

次に x=7+20m を x≡4 (mod 7) に代入する。7+20m≡0+6m≡4 (mod 7) より 6m≡4 (mod 7)。6≡-1 なので -m≡4、すなわち m≡-4≡3 (mod 7)。よって x=7+60=67 となり、x≡67 (mod 140)。

検算：67=4·16+3 なので mod 4 で 3。67=5·13+2 なので mod 5 で 2。67=7·9+4 なので mod 7 で 4。いずれも条件を満たす。

解は 67+140t で、最小の正の整数は 67。