>>573
任意の奇素数 p について、p-1 は偶数、よって p-1 = k*2^n （k はある奇数、n はある正整数）と書ける。
従って、その問題は k または n に何らかの条件をつけないと詰まらないものだろう。

たとえば n を1つ固定し k をパラメータにとるとすれば、
引き合いに出されているLucasの定理より、F_m (m≧n-2)の素因数が条件を満たし、
これは無限に存在する。
牛刀的だが、Dirichletの算術級数定理を用いてもいい。

それでは逆に、正整数 k を1つ固定して考えるとき、k*2^n + 1 が素数であるような
正整数 n は無限に存在するのだろうか。
kが1または2のべきの場合はFermat素数を求めることになるが、これは周知の通り未解決問題である。
また、適当にkを選べば k*2^n + 1 がいかなる正整数 n についても
素数とならないことがSierpinskiによって示されている。（本スレ >>77, >>78 を参照）