こんにちは。東久留米市の学習塾塾長です。
予報通りシベリア高気圧が日本列島を覆い、全国的に秋晴れになりました。この高気圧は直ぐに東へ移動してしまいますが、また新たに北西から高気圧がやってきて、しばらくの間、大きな崩れはないようです。
さて、今回は２００１年日本数学オリンピック予選に出題された整数問題を取り上げます。
問題は、
「２００１をある正の整数ｎで割ったところ、余りは１１４になった。このようなｎのうち、最小のものを求めよ。ただし、ｎ＞１１４である。」
です。
まず、問題文の内容を立式しましょう。
２００１をｎで割ったときの商をＱとすると、
２００１÷ｎ＝Ｑ・・・１１４
で、これから、
ｎＱ＋１１４＝２００１
ｎＱ＝１８８７
が成り立ち、これはｎが１８８７の約数であることを意味しています。
そこで、１８８７を素因数分解すると、
１８８７＝３×１７×３７
から、１８８７の約数は、
１，３，１７，３７，５１，１１１，６２９，１８８７
です。
ここで、ｎ＞１１４から、条件をみたすｎで最小値のものは６２９で、これが答えです。
以上のように、簡単に答えが見つかるのですが、１８８７の素因数分解が難しいかもしれません。
１８８７の各位の数の和は、１＋８＋８＋７＝２４で、これは３の倍数ですから、１８８７は３で割り切れ、その商は６２９になります。
もし、６２９の素因数分解が見つけられずに答えを６２９と書いても正解になるのですが、ここでは、少し６２９の約数探しを調べてみましょう。
６２９は、２、３、５の倍数でないので、２，４，６，８，・・・、３，６，９，１２，・・・、５，１０，１５，２０，・・・の倍数ではありません。
つまり、６２９の約数の候補は、７，１１，１３，１７，１９，・・・になります。
あとは、６２９÷７＝８９・・・６、６２９÷１１＝５７・・・２、６２９÷１３＝４８・・・５、６２９÷１７＝３７、のように、割り算を繰り返せば、１７が約数であることが判ります。（もちろん、倍数の判定法を使ってもＯＫです）
ところが、なかなか割り切れない場合、いつまで割り算を繰り返せばいいのかが気になるところです。
そんなときには、
「合成数ｎは１より大きく√ｎを超えない約数をもつ」
または
「正の整数ｎが√ｎを越えない最大の整数以下のすべての素数で割り切れなければ、ｎは素数」
を使うとよいでしょう。
実際に、「合成数ｎは１より大きく√ｎを超えない約数をもつ」を６２９に適用してみましょう。
まず、
２５^2＝６２５＜６２９＜６７６＝２６^2
から
２５＜√６２９＜２６
なので、６２９が合成数であれば、２５以下の約数をもつことになります。
ここで、６２９は、２、３、５の倍数でないので、それらを除いた２５以下の整数は、７，１１，１３，１７，１９，２３の６個になり、これらの数で６２９を割り算すれば、６２９が合成数か素数かが判ります。
合成数、素数の調べ方は頭に入れておくとよいかもしれません。
予報通りシベリア高気圧が日本列島を覆い、全国的に秋晴れになりました。この高気圧は直ぐに東へ移動してしまいますが、また新たに北西から高気圧がやってきて、しばらくの間、大きな崩れはないようです。
さて、今回は２００１年日本数学オリンピック予選に出題された整数問題を取り上げます。
問題は、
「２００１をある正の整数ｎで割ったところ、余りは１１４になった。このようなｎのうち、最小のものを求めよ。ただし、ｎ＞１１４である。」
です。
まず、問題文の内容を立式しましょう。
２００１をｎで割ったときの商をＱとすると、
２００１÷ｎ＝Ｑ・・・１１４
で、これから、
ｎＱ＋１１４＝２００１
ｎＱ＝１８８７
が成り立ち、これはｎが１８８７の約数であることを意味しています。
そこで、１８８７を素因数分解すると、
１８８７＝３×１７×３７
から、１８８７の約数は、
１，３，１７，３７，５１，１１１，６２９，１８８７
です。
ここで、ｎ＞１１４から、条件をみたすｎで最小値のものは６２９で、これが答えです。
以上のように、簡単に答えが見つかるのですが、１８８７の素因数分解が難しいかもしれません。
１８８７の各位の数の和は、１＋８＋８＋７＝２４で、これは３の倍数ですから、１８８７は３で割り切れ、その商は６２９になります。
もし、６２９の素因数分解が見つけられずに答えを６２９と書いても正解になるのですが、ここでは、少し６２９の約数探しを調べてみましょう。
６２９は、２、３、５の倍数でないので、２，４，６，８，・・・、３，６，９，１２，・・・、５，１０，１５，２０，・・・の倍数ではありません。
つまり、６２９の約数の候補は、７，１１，１３，１７，１９，・・・になります。
あとは、６２９÷７＝８９・・・６、６２９÷１１＝５７・・・２、６２９÷１３＝４８・・・５、６２９÷１７＝３７、のように、割り算を繰り返せば、１７が約数であることが判ります。（もちろん、倍数の判定法を使ってもＯＫです）
ところが、なかなか割り切れない場合、いつまで割り算を繰り返せばいいのかが気になるところです。
そんなときには、
「合成数ｎは１より大きく√ｎを超えない約数をもつ」
または
「正の整数ｎが√ｎを越えない最大の整数以下のすべての素数で割り切れなければ、ｎは素数」
を使うとよいでしょう。
実際に、「合成数ｎは１より大きく√ｎを超えない約数をもつ」を６２９に適用してみましょう。
まず、
２５^2＝６２５＜６２９＜６７６＝２６^2
から
２５＜√６２９＜２６
なので、６２９が合成数であれば、２５以下の約数をもつことになります。
ここで、６２９は、２、３、５の倍数でないので、それらを除いた２５以下の整数は、７，１１，１３，１７，１９，２３の６個になり、これらの数で６２９を割り算すれば、６２９が合成数か素数かが判ります。
合成数、素数の調べ方は頭に入れておくとよいかもしれません。
