皆さん、mod計算を積極的に使いましょう!
整数論の問題を解く際に、modの使い方に慣れていると大抵は解けます!
高校生の方は身につければ入試には非常に有利だし、大学生の方もあまりのすっきりさに目を疑うでしょう。
ここでは、あまり複雑に述べることはせず、まずはどういったものか、知らない人は知っておいた方がいいと思います^^
<modの定義>
例えば、『』ならば『aとbはmを法として合同』という言い方をします。砕いて言えば、『a-bはmで割り切れる』ってことです。
さて、どのくらい整数問題あっさりと解くことができるのか数検1級(2次)の問題でみてみたいかと思います。
(僕が受けた第110回の問題です)
問.p(≧2)は正の整数で3の倍数でないとします。このとき
はで割り切れることを証明しなさい。
(整数論に関しては一寸ややこしい回文数もありますが、これは後に問いのみ紹介しますのでやってみたい方は挑戦してみてください。これも1級の問題です)
(解答例)
まず、ですから
となります。
(鄯)(kは自然数)のとき
よって、で割り切れる。
(鄱)(k=0或はkは自然数)のとき
よって、で割り切れる。
故に、割り切れることがわかりますね□
どうでしょうか?非常に簡単ですよね^^
まともにやればもう少し面倒くさいことになると思いますが、modの威力を分っていただけたでしょうか。
次に、おまけ問題として『回文数』のやつを紹介しますね。
問.回文数とは数字列を逆順にしても同じになる数のことで、1746471はその1つの例です。
p(≧3)進法で、1≦m≦p-1のとき
と表される回文数を考えます。
は完全平方数となることを示すために
となるを求めなさい。
※根気と忍耐力のある方は是非ともやってみてくださいね^^
(modや大学の知識は一切使いません)