問題文
$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: 解答の一部にミスがあったため修正しました。
