問題
次の問に答えよ。
を満たす整数の組を一組求めよ。
を満たす整数の組の中でが最小となるもの、およびその最小値を求めよ。
方針
中国式剰余定理を題材にした問題である。与えられた式をで割ったものを考えると、先が見えてくる。
解答
である。したがって、に対して、での剰余を考えると、となる。この剰余式を解くと、順にとなる。したがって、を整数として、とおける。これをに代入すると、となり、整理すると、となる。よって、である。これを満たすとして、適当にを取ることができて、その時となる。これはを満たす。
から、を満たすの組は、とおける。は整数を自由に動く事ができる(このときとは自由に動けない)ので、を小さくするには、をそれぞれ小さくすれば良い。であるから、のときは最小である。このとき、で、となる。よって、が最小になるのはのときで、の最小値はとなる
解説
日本では古来から百五減算という数遊びが知られている。これは、塵劫記という江戸時代の算術書に記載されたもので、次のような問題である。
で割るとあまり、で割るとあまり、で割ると余る一番小さい数は何か?
これには次のような巧妙な解法が知られている。というマジックナンバーを考える。なぜこのような数を考えるかというと、であるから、ある数をで割った余りを順にとすると、は、で割るとあまり、で割るとあまり、で割るとあまる数を代表しているのである。これがより大きい時は、を引き、マイナスになっている時はの整数倍を足せば良い。を引くので百五減算という訳である。
上の問題の答えは、として、これはよりも大きいので、となる。実際にをで割った確かめると良い。
以下が中国式剰余定理であり、この定理のおかげで百五減算や、上の東京工業大学の問題に解が存在することが保証されている。
はどのつをとっても互いに素な自然数として、を任意の整数とする。このとき、を満たす整数が、からの中に、ただ一つ存在する。
この定理は大学の群論で学ぶので、今はあまり気にしないでも問題ない。
関連問題
2000年京都大学後期理系数学問題3 を満たす整数(格子点)の存在
関連リンク
東京工業大学
東京工業大学の教育、研究、社会連携、国際交流などの活動、東京工業大学に関する概要や最新情報をご覧頂けます。
コメント