先日紹介した NSA’s Puzzle Periodical(※1)の６月の問題で、Chimese remainder theorem(※2)が紹介されています。
整数 n1 で割ると a1 が余り、整数 n2 で割ると a2 が余る整数 x は何ですか？ というよくある問題の研究です。
解き方として
m1n1 + m2n2 = 1
となる m1 と m2 を見つければ、求める x は
x = a1m2n2 + a2m1n1
が紹介されています。
例えば ３で割れば２余り、７で割れば１余る整数は、
(-2)x3 + 1×7 =1 と -2 と 1 を見つけることができ
x = 2x1x7 + 1x(-2)x3 = 8 と答えを導き出せます。もちろんこの 8 に 3 と 7 の最小公倍数 21 を加えていった数字も条件に当てはまります。
それでは問題です。
163 で割れば 7 余り、571 で割れば 3 余る整数は何でしょう？
数字が大きくなるとちょっと大変そうですが、比率の考えを入れて解いてみてください。
(※1) https://www.nsa.gov/news-features/puzzles-activities/puzzle-periodical/
(※2) https://en.wikipedia.org/wiki/Chinese_remainder_theorem
