今回はフェルマーの小定理に関する問題です。が素数であることは周知の事実ですよね・・・(笑)?
《問題#18》
をで割ったときの余りを求めよ。
(創作問題)
が素数であることを使えば簡単に示すことができますが、もちろんフェルマーの小定理を知らなくても初等的に解決することができます。
創作整数問題#17(解き方)
の倍数でない整数の における平方剰余がとなることに着目して話を進めます。詳しい証明は整数第3章第1節問題#B005を参照してもらえればと思いますが、実戦上は解答の隅に
「 となるから、の倍数でない整数の平方をで割ったときの余りはとなる」
などと簡単に書いておくのが無難でしょう。
右辺はの倍数ではないのではの倍数にはなりません。するとをで割ったときの余りはに限られますから、右辺についてもで割ったときの余りがとなる必要があります。をで割ったときの余りは、が奇数のとき、が偶数のときとなるので、は偶数でなければなりません。そこで正の整数を用いて と置くと、与式は と変形できます。であり、 ですからこれを満たす組の候補はの2組に限られます。それぞれに対応するので、求める組はとなります。
(コメント)
必要条件を文字化するという操作(今回で言うと という置き換えがこれに当たります)は整数問題を攻略する上で非常に大切な手法の一つです。置き換えによって解をどんどん絞り込んでいきましょう。問題#17は類題が作りやすいタイプの整数問題なので数年に一度はどこかの大学でこういった問題が出題されているような気がします。