問題文
$65537=2^{16}+1$ が素数かどうか、計算機を使わずに判定したい。以下では $p$ を3以上の素数として、⑴から⑸の問いに答えよ。
⑴ $2^p$ を $p$ で割ったあまりは $p$ によらないことを示し、その値を求めよ。
⑵ $65537$ が $p$ で割り切れるとき、$2^n$ を $p$ で割ったあまりが $1$ になるような最小の自然数 $n$ を求めよ。
⑶ $65537$ が $p$ で割り切れるとき、$p$ を $32$ で割ったあまりとしてあり得る値をすべて求めよ。
⑷ $ p < \sqrt{65537}$ をみたす $p$ であって、$p$ を $32$ で割ったあまりが⑶で求めた数になるようなものをすべて求めよ。
⑸ 以上の結果から、$65537$ が素数かどうか判定せよ。
解答形式
以下の指示に従って、すべて半角数字で入力せよ。
⑴から⑷までの答えはいずれも非負整数である。
⑴の答えを1行目に入力せよ。
⑵の答えを2行目に入力せよ。
⑶の答えは1つずつ改行して3,4,......i 行目に小さい順に入力せよ。
⑷の答えも1つずつ改行してi+1,i+2, ......j行目に小さい順に入力せよ。
最後に⑸の答えとして、$65537$ が素数であれば1を、そうでなければ0を入力せよ。
20/06/19: 解答の一部にミスがあったため修正しました。
ヒント1
全体的に、合同式を使って議論すると見通しがよい。
⑴ $2^p=(1+1)^p$ として二項定理を用いよ。二項係数はすべて自然数となることに注意せよ。
ヒント2
⑵ $65537$ が $p$ で割り切れるとき、 $2^{32}$ を $p$ で割ったあまりは $1$ となることに留意せよ。
たとえば $n=4,5$ を考えて、$2^{4}$ や $2^{5}$ を $p$ で割ったあまりが $1$ であるとすると、 $65537$ が $p$ で割り切れることに矛盾することを示せ。
ヒント3
⑶ ⑴の結果より、 $2^{p-1}$ を $p$ で割ったあまりを求め、これを⑵の結果と見比べよ。実は答えは1つに限られる。そのことを背理法で示せ。
ヒント4
⑷ 一般に、自然数 $N$ が素数かどうか判定するには、$\sqrt{N}$ 以下の素数で割り切れるかどうか調べればよいことに注意せよ。
ヒント5
⑸ $65537$がある素数で割り切れるかどうかを、$\sqrt{65537}$ 以下の素数についてすべて割り算して判定するのは大変である。⑴から⑷の議論によって、$65537$を割り切る可能性のある素数 $p$ の候補を絞ることができたはずである。絞られた $p$ の候補について、実際に $65537$ を割り切るかどうか調べてみよ。
スポンサーリンク
解答提出
おすすめ問題
この問題を解いた人はこんな問題も解いています
