素数全書練習問題1.17 - Finite Groups Fun 有限群あるいはちょこっと計算ファンの日記

つかみどころがわからなくて、かなり長い間考えていた問題である。
が、先日出張中の宿でいろいろやっているうちに気がついた。modulo 3 で系列を追いかけるのである。

スタートの素数をPとする。P=3 でなければ、Pの3での余りは1か2である。仮にP≡1(mod 3)とすると 2P+1は3で割れるため素数ではない。そこで題意の系列は常に2倍して1を引くという手続きで作られることになるので N項目は $(P-1)\cdot 2^{N-1}+1$ の形をしていることが帰納法でわかる。この系列が素数の無限列とならないのは、N=Pとするとフェルマーの小定理より $2^{P-1}\equiv 1 (mod P)$ であるから $(P-1)\cdot 2^{P-1}+1\equiv (P-1)\cdot 1+1 \equiv 0(mod P)$ とPで割りきれてしまうためである。

同様にP≡2(mod 3)の場合、題意の系列は常に2倍して1を足すという手続きで作られ、 N項目は $(P+1)\cdot 2^{N-1}-1$ となる。
まったく同じ論法でN=Pのとき、Pで割れてしまうため、やはり素数の無限列とはならない。

P=3のときは 5か7が次の素数だが、これ以降は上記の論法が成立するため、やはり無限には続かない。実際、5,11,23,47 および 7,13　と途切れる。

なんとか解けたものの前後との関係がよくわからない問題であった。