「２^13−１が素数であることを示すために、まず、√（２^13−１）以下の素数で、２６で割っ
て１余るものを全て求める」
という例が出されているのですが、この場合は、３４で割って１余る素数を探せば良いので
しょうか。
DD++さんからのコメントです。（令和３年５月３０日付け）
「２^13−１が素数であることを示すために、まず、√（２^13−１）以下の素数で、２６で割っ
て１余るものを全て求める」
は、おそらく次に、
「それら全てで 2^13-1 を割ってみる」
「割り切れるものがなかったので 2^13-1 は素数と示された」
と続くのだと思います。それで、なぜ 2^13-1 が素数と言えるのか。
その根拠は、
(1) ある自然数が、その平方根以下の素因数をもたないなら、その自然数自身が素数である
(2) 2^13-1 の素因数は奇数しかありえない
(3) 2^13-1 の素因数は 13 で割って 1 余るものしかありえない
の 3 つが言えるからです。
(1) の総当たりをする上で、(2)(3) から 13 で割って 1 余る奇素数以外はやってみるまでも
ない、というわけですね。
(1) は一般的な定理、(2) は少し考えれば明らか、なので (3) だけ解説しておきます。
p が 2^13-1 の素因数とします。このとき、(2) より p は奇素数なので、フェルマーの小定理
より、2^(p-1)-1 は p の倍数です。このとき、
(2^(p-1)-1) - (2^13-1) = 2^13*(2^(p-14)-1)
を考えると、p の倍数同士の差はまた p の倍数であることと、p は奇数であることから、
2^(p-14)-1 もまた p の倍数になります。すると、今度は、
(2^(p-14)-1) - (2^13-1) = 2^13*(2^(p-27)-1)
という式から、2^(p-27)-1 も p の倍数となります。
（※ p＜27 だったら、みたいな厳密性は今はちょっと無視しています）
これをユークリッドの互除法っぽく繰り返すと、最終的に、
13 と p-1 の最大公約数を g として、2^g-1 が p の倍数となるはずです。
（きちんと証明したければ、拡張ユークリッドの互除法を用いてください）
ところで、13 は素数なので、g は 1 か 13 しかありえませんね。そして、g=1 だと、1 が p の
倍数という話になって明らかにおかしいですね。
よって、g=13 であり、p は 13 で割った余りが 1 でなくてはならない、ということになります。
＃問題は、2^17-1 とのことですが、上の議論の 13 を全て 17 に書き換えても成立するかど
うかを考えればよいかと思います。
（コメント） 掲示板の方ではDD++さんに１分差で先を越されました。とりあえずの回答です。
フェルマーの小定理から、2^16-1≡０（mod 17）なので、2^16は、17で割って１余る数である。
よって、2^17-1は、34、即ち、17で割って１余る数となる。
2^17-1＝131071 で、√（2^17-1）=362.033 から、2から362までの素数 2,3,5,・・・,353,359
で割り切れるかどうかを調べればよい。すべてで割り切れなければ素数となる。
ただし、確認が必要な素数は全部で７２個もあり、その検証は現実的でない。
DD++さんの指針に従って計算してみた。
2^17-1の素因数をｐとおくと、 2^17-1≡０ （ｍｏｄ ｐ） が成り立つ。
このとき、ｐは奇素数で、フェルマーの小定理より、 2^(p-1)-1≡０ （ｍｏｄ ｐ）
よって、 2^(p-1)≡1 （ｍｏｄ ｐ） 、2^17≡1 （ｍｏｄ ｐ） が成り立つ。
p-1 と 17 の最大公約数を g とすると、ある整数 ｍ、ｎ があって、 （p-1）ｍ＋17ｎ＝ｇ
このとき、 2^g＝（2^(p-1)）^m・（2^17）^n≡1 （ｍｏｄ ｐ） すなわち、2^g-1≡０ （ｍｏｄ ｐ）
ここで、17 は素数なので、g は 1 または 17 であるが、g=1 は不適。よって、ｇ＝17
以上から、p-1≡０ （ｍｏｄ 17） で、ｐは１７で割って１余る素数となる。
2,3,5,・・・,353,359 の中で、この条件を満たす素数は、
１０３２ 、１３７ 、２３９ 、３０７
これらは何れも 2^17-1＝131071 を割り切ることはない。
以上から、 2^17-1＝131071 は素数である。
DD++さんからのコメントです。（令和３年５月３０日付け）
「任意の自然数 N について、N を 34 で割った余りが 1 ならば N の素因数を 34 で割った
余りが 1」は一般的には偽ですね。
（反例：１５９９＝３４×４７＋１で、１５９９の素因数は、３、１３、４１）
N = 2^17-1 の場合には、その形の特殊性からたまたまそれが成り立つことを証明する必
要があると思います。
（コメント） DD++さん、ご指摘ありがとうございます。自分自身、モヤモヤした部分が解決し
て安心しました。上記（コメント）の証明は、修正済みです。
