2で割り切れる／割り切れない

のどちらであるかは，末位（最後の１けた）の数が偶数か／奇数かで判定できる．
　例えば，314は末位の数4が偶数だから2で割り切れる．123は末位の数3が奇数だから2で割り切れない．
　一般に，ある数 n がある数 p で割り切れるか割り切れないかという問題は，割り算で決めるのがふつうであるが，2で割り切れる／割り切れないの場合，割り算をする人はいない．だれでも上の例のように考える．
　次の各場合についても，簡単な判定法が知られている．

　　3で割り切れる／割り切れない
　　4で割り切れる／割り切れない
　　5で割り切れる／割り切れない
　　8で割り切れる／割り切れない
　　9で割り切れる／割り切れない
　　25で割り切れる／割り切れない

　これらの判定法は諸君も知っていると思うが，証明はできるかな？　証明を知りたい人は上の各項目をクリックしてみよ．
　変わったところでは，

　　11で割り切れる／割り切れない

の判定法がある．
　ものごとを処理するとき，できるだけ手軽な方法で済ませたいと思うのは当然のことである．上のような判定法は，省エネ法，低コスト法といってよいであろう．
　以上が，割り切れる／割り切れないの問題の定型の（型にはまった）判定法である．
　それでは，

　　7で割り切れる／割り切れない

について手軽な判定法はあるのだろうか．
　「そんな話は聞いたこともない」という人がいよう，その通り，これには判定法はない．
　例えば，2345が7で割り切れるかどうか，割って確かめるのが早そうである．
　それでは，もっと大きい数による割り切れる／割り切れないの問題も割り算以外に方法はないのだろうか．

　割り切れる／割り切れないの問題の１つとして，素因数分解の問題がある．
　ここでは，

　　　　整数 n を素因数分解する

という問題について考えてみよう．
　n の素因数を見つけるには，考えられるすべての素数 2，3，5，7，11，13，……について，割り切れるか／割り切れないかためしてみなければならない．

　　　　n が素数でなければ，n は以下のある素数で割り切れる．

　しかし，n の素因数を見つけるために，いろいろな素数について割り算を繰り返すことは大変わずらわしいことである．そこで，すばやく素因数を見つける工夫をしてみよう．

　　例として，2047の素因数分解を考えてみよう．23*89
　　前項の判定法により，2047は2，3，5，11のどれでも割り切れない．
　　2047と7の倍数2100との差は53だから，7では割り切れない．
　　2047に13を加えると2060で206＝103×2だから，13では割り切れない．
　　2047から17を引くと2030で，203＋17＝220だから，17では割り切れない．
　　2047から19の倍数1900を引くと147で，これと190との差は53で，19では割り切れない．
　　2047に23を加えると2070で，207＝9×23となるから，23では割り切れる．
　　ここではじめて割り算2047÷23＝89を実行して，素因数分解
　　　　　　　　　　2047＝23×89
が得られる．

　この問題「2047の素因数分解」においては，最後の答だけが求められている．しかも，問題解決の道中は試行錯誤そのものである．この答がどのように求められたかは問題にならない．どう解こうと自由である．
　このようなとき，その場面に応じた問題解決法を見つけることが肝要である．
　臨機応変ということばがあてはまる場面である．