ある自然数が「7で割ると5余り、13で割ると8余る」という条件を満たすとき、そのような数がどのように構成され、3桁の範囲でいくつ存在するのかは、合同式と整数論の基本的な考え方で整理できる。本記事ではこの問題を体系的に解説する。
問題の条件を合同式で整理する
まず与えられた条件は次のように合同式で表すことができる。
n ≡ 5 (mod 7)、n ≡ 8 (mod 13) という形である。
例えば「7で割って5余る数」は7k+5と表せるように、同様の構造で13の条件と組み合わせることになる。
解の構造と周期性の理解
2つの合同条件を同時に満たす数は、一定の周期で繰り返し現れる性質を持つ。
これは中国剰余定理の基本的な考え方で、最小公倍数91を周期として解が並ぶ。
例えば一つ解が見つかれば、それに91を足すことで次の解が得られる。
具体的な解の導出
まずn ≡ 5 (mod 7)より n = 7k + 5 とおく。
これを13の条件に代入して整理すると、kの値を求めることで最小解が決まる。
計算すると最小の解は n = 47 となる。
3桁の範囲での解の個数
解は91ずつ増加するため、一般形は n = 47 + 91t と表される。
これが100以上999以下に収まる範囲を調べることで個数が求まる。
例えばt=1で138、t=10で957となり、この範囲内に収まる整数を数える。
最大値と最小値の決定
最小の3桁解は138（t=1）、最大の3桁解は957（t=10）となる。
このように周期性を利用することで、すべての解を機械的に列挙せずに求めることができる。
したがって条件を満たす3桁の数は10個存在する。
まとめ
本問題は合同式と中国剰余定理を用いることで体系的に解くことができる典型的な整数問題である。
解は周期91で現れ、3桁の範囲では一定間隔で10個存在する。
このような問題は構造を理解することで計算量を大幅に減らすことができる。
コメント