創作整数問題#17解法&創作整数問題#18



今回はフェルマーの小定理に関する問題です。2017が素数であることは周知の事実ですよね・・・(笑)?


《問題#18》

220172017で割ったときの余りを求めよ。

(創作問題)


2017が素数であることを使えば簡単に示すことができますが、もちろんフェルマーの小定理を知らなくても初等的に解決することができます。

 

 

» 答えはこちら

答えは \colorred2 です。

» 閉じる


創作整数問題#17(解き方)


3の倍数でない整数の mod 3 における平方剰余が1となることに着目して話を進めます。詳しい証明は整数第3章第1節問題#B005を参照してもらえればと思いますが、実戦上は解答の隅に

(3N±1)2=3(3N2±2N)+1 となるから、3の倍数でない整数の平方を3で割ったときの余りは1となる」

などと簡単に書いておくのが無難でしょう。

右辺は3の倍数ではないのでm3の倍数にはなりません。するとm23で割ったときの余りは1に限られますから、右辺についても3で割ったときの余りが1となる必要があります。2n3で割ったときの余りは、nが奇数のとき2nが偶数のとき1となるので、nは偶数でなければなりません。そこで正の整数kを用いて n=2k と置くと、与式はm2+15=22k 15=22km2 15=(2km)(2k+m)と変形できます。15=35であり、2km<2k+m ですからこれを満たす組(2km,2k+m)の候補は(1,15)(3,5)の2組に限られます。それぞれ(m,n)=(7,6)(1,4)に対応するので、求める組(m,n)\colorred(m,n)=(1,4)(7,6)となります。


(コメント)

必要条件を文字化するという操作(今回で言うと n=2k という置き換えがこれに当たります)は整数問題を攻略する上で非常に大切な手法の一つです。置き換えによって解をどんどん絞り込んでいきましょう。問題#17は類題が作りやすいタイプの整数問題なので数年に一度はどこかの大学でこういった問題が出題されているような気がします。

 

コメントを残す

メールアドレスが公開されることはありません。 が付いている欄は必須項目です

©Copyright 2017-2025 理系のための備忘録 All Rights Reserved.