[math][東京工業大学]2018年度前期東京工業大学数学問題2

問題
方針
解答
解説
関連問題
関連リンク

問題

次の問に答えよ。
$(1)$ $35x + 91y + 65z = 3$を満たす整数の組$(x, y, z)$を一組求めよ。
$(2)$ $35x + 91y + 65z = 3$を満たす整数の組$(x, y, z)$の中で$x^2+y^2$が最小となるもの、およびその最小値を求めよ。

方針

中国式剰余定理を題材にした問題である。与えられた式を$5, 7, 13$で割ったものを考えると、先が見えてくる。

解答

$(1)$ $35 = 5\times7, 91 = 7\times 13, 65 = 13\times5$である。したがって、$35x + 91y + 65z = 3$に対して、$5, 7, 13$での剰余を考えると、$$\begin{cases}y\equiv 3 \pmod{5} \\ 2z \equiv 3 \pmod{7} \\ 9x\equiv 3 \pmod{13} \end{cases}$$となる。この剰余式を解くと、順に$y \equiv 3 \pmod{5}, z \equiv 5 \pmod{7}, x \equiv 9 \pmod{13}$となる。したがって、$p, q, r$を整数として、$$\begin{cases}x = 13p+9 \\ y = 5q + 3 \\ z = 7r + 5\end{cases}$$とおける。これを$35x + 91y + 65z = 3$に代入すると、$$35(13p+9) + 91(5q + 3)+ 65(7r+5) = 3$$となり、整理すると、$$5\times7\times 13 (p+q+r) = -910 = -5\times 7\times 13\times 2$$となる。よって、$p+q+r = -2$である。これを満たす$p, q, r$として、適当に$p = -1, q = -1, r = 0$を取ることができて、その時$\underline{x = -4, y = -2, z = 5}$となる。これは$35x + 91y + 65z = 3$を満たす。

$(2)$ $(1)$から、$35x + 91y+65z = 3$を満たす$(x, y, z)$の組は、$$\begin{cases}x = 13p + 9 \\ y = 5q + 3 \\ z = 7r + 5 \\ p +q + r = -2\end{cases}$$とおける。$p, q$は整数を自由に動く事ができる（このとき$r = -2-p-q$と$r$は自由に動けない）ので、$x^2+y^2$を小さくするには、$\mid x\mid, \mid y\mid$をそれぞれ小さくすれば良い。$$\begin{eqnarray}x & = & \cdots, -17, -4, 9, 22, \cdots \\ y & = & \cdots, -7, -2, 3, 8, \cdots \end{eqnarray}$$であるから、$x = -4, y = -2\ (p = -1, q = -1)$のとき$x^2+y^2$は最小である。このとき、$r = 0$で、$z = 5$となる。よって、$x^2+y^2$が最小になるのは$\underline{(x, y, z) = (-4, -2, 5)}$のときで、$x^2+y^2$の最小値は$\underline{20}$となる

解説

日本では古来から百五減算という数遊びが知られている。これは、塵劫記という江戸時代の算術書に記載されたもので、次のような問題である。

$3$で割ると$2$あまり、$5$で割ると$1$あまり、$7$で割ると$2$余る一番小さい数は何か？

これには次のような巧妙な解法が知られている。$70, 21, 15$というマジックナンバーを考える。なぜこのような数を考えるかというと、$$\begin{cases}70\equiv 1 \pmod{3}\\ 21 \equiv 1 \pmod{5}\\ 15 \equiv 1\pmod{7}\end{cases}$$であるから、ある数$x$を$3, 5, 7$で割った余りを順に$a, b, c$とすると、$$70a + 21b + 15c$$は、$3$で割ると$a$あまり、$5$で割ると$b$あまり、$7$で割ると$c$あまる数を代表しているのである。これが$3\times 5\times 7 = 105$より大きい時は、$105$を引き、マイナスになっている時は$105$の整数倍を足せば良い。$105$を引くので百五減算という訳である。

上の問題の答えは、$70\times 2 + 21\times 1 + 15\times 2 = 191$として、これは$105$よりも大きいので、$191-105 = 86$となる。実際に$86$を$3, 5, 7$で割った確かめると良い。

以下が中国式剰余定理であり、この定理のおかげで百五減算や、上の東京工業大学の問題に解が存在することが保証されている。

$p, q, r$はどの$2$つをとっても互いに素な自然数として、$a, b, c$を任意の整数とする。このとき、$$\begin{eqnarray}x & \equiv& a \pmod{p} \\ y & \equiv & b \pmod{q} \\ z & \equiv & c \pmod{r} \end{eqnarray}$$を満たす整数$x$が、$0$から$pqr-1$の中に、ただ一つ存在する。

この定理は大学の群論で学ぶので、今はあまり気にしないでも問題ない。