ホーム >> 整数 >> 孫子の問題
hide or visible

問題の説明

この問題は,中国の算術書,『孫子算経』に書かれている問題です.(数字は多少異なるかもしれませんが.) 実は,$3\times5\times 7=105$ 以下で,問題の条件を満たすものがたったひとつだけ存在します.したがって,当てずっぽうで $105$ 以下の数を考えても,相当優れた数覚を持っていない限り,まず当たりません.

不定方程式を用いる解法

$3$ で割って $1$ 余り,$5$ で割って $2$ 余り,$7$ で割って $3$ 余る正の整数を $N$ とすると,整数 $x,y,z$ を用いて, $$N=3x+1=5y+2=7z+3 $$ とかけます.これより,$3x-5y=1,5y-7z=1$ です.
$3x-5y=1$ を眺めると,$(x,y)=(2,1)$ がひとつの整数解であることに気がつきます.したがって, $$3x-5y=1$$ $$3\cdot2-5\cdot1=1$$ 辺々ひくと, $$3(x-2)=5(y-1)$$ $3,5$ は互いに素なので,整数 $m$ を用いて, $$x=5m+2,y=3m+1$$ とかけます.$y=3m+1$ を $5y-7z=1$ に代入して整理すると, $$z=\frac{5y-1}{7}=\frac{5(3m+1)-1}{7}=\frac{15m+4}{7}=2m+\frac{m+4}{7}$$ $z$ は整数なので,整数 $n$ があって,$m+4=7n$ とかけます.以上より, $$N=3x+1=15m+7=105n-53$$ $$N=3y+2=15m+7=105n-53$$ $$N=7z+3=15m+7=105n-53$$ よって,条件を満たす最小の正の整数は,$n=1$ のときで, $$\boxed{52}$$ が答えとなります.

合同式を用いる解法

合同式をご存知の方は,連立合同式を解く方法がおすすめです.
連立合同式 \begin{eqnarray} \left\{ \begin{array}{l} x \equiv 1 (mod 3)\\ x \equiv 2 (mod 5)\\ x \equiv 3 (mod 7)\\ \end{array} \right. \end{eqnarray} を考えます.まず,はじめの式より,整数 $y$ を用いて,$x=3y+1$ とかけるので,これを第二式に代入すると, $$3y \equiv 1 (mod 5)$$ となります.この1次合同式の解は,$y \equiv 2 (mod 5)$ です.($y$ に $0$ から $4$ を代入して,合同式を満たすかチェックするのです.)
よって,整数 $z$ を用いて,$y=5z+2$ とかけます.したがって,$x=15z+7$ です.これを第三式に代入すると, $$15z \equiv -4 (mod 7)$$ ですが,この $1$ 次合同式の解は, $z \equiv 3 (mod 7)$ です.よって,整数 $w$ を用いて,$z=7w+3$ とかけます.これより, $$x=105w+52$$ とかけることがわかります.したがって,条件を満たす最小の正の整数は,$w=0$ のときで, $$\boxed{52}$$ が答えとなります.