フェルマーの小定理で見るメルセンヌ素数

自分は独学で数学を勉強していますので、誤った内容になっている場合があります。温かい目で見ていただき、誤っている部分がありましたら、ご指摘いただけると幸いです。

①フェルマーの小定理

$p$が素数で、$a$が$p$の倍数でない($p$と互いに素な）整数のとき、$a^{p-1}\equiv 1\quad $(mod $p$)（$a$の$p-1$乗を$p$で割った余りは$1$になる）
を用いると、$a = 2$のとき、$2$以外の素数$p$では下記が成り立つ。
$2^p -1= 2p*n+1$ ($n$は自然数)

②メルセンヌ素数

メルセンヌ素数は$2^p -1$($p$は素数)の形で表すことができる素数のことである。
$p=2$のとき、$2^p -1=3$より、$2^p -1$はメルセンヌ素数
$p=11$のとき、$2^p -1=2047=23*89$より、$2^p -1$はメルセンヌ素数ではない

①フェルマーの小定理より、$p$は素数、$n$が任意の自然数の場合、
$2^p -1= 2p*n+1$ ($n$は自然数)と表すことができる。
$2^p -1$が素数でない場合、$2^p -1 = a *b$($a,b ≠ 1$,$a,bは自然数$)とする。
$a\equiv a^{'}\quad $(mod $2p$)
$b\equiv b^{'}\quad $(mod $2p$)
とした場合、任意の自然数$l,m$を用いて、
$2^p -1 = a *b = (2lp + a^{'})(2mp + b^{'})=2p(2lmp + a^{'}m + b^{'}l) +a^{'}b^{'} = 2pn+1$・・(※)
よって、$a^{'} = 1,b^{'} = 1$となる。
したがって、メルセンヌ素数でない場合、
$2^p -1= (2l_{1}p+1)(2l_{2}p+1)...(2l_{m}p+1)$($l_1,l_2,...,l_{m}は任意の自然数$)と書ける。

また、$(2l_{m}p+1)$はそれぞれ、素数となる。
素数でない場合、$(2l_{m}p+1) = a * b$$($a,b ≠ 1$,$a,bは自然数$)とした場合、(※)式と同様の式変形を行うことで、素数のみの素因数分解に変形できる。

③メルセンス素数を求めるアルゴリズム

②と素数表を用いると下記のようになる。

int p #素となる素数
int prime_number = 2p+1 #(2lp+1)で表される power(2,p)-1の約数候補
int[] PrimeNumberTable #素数表
while(power(2,(p+1)/2) -1 > prime_number){
    # power(2,p)-1の1/2乗を超えない場合続ける
    if(prime_number in PrimeNumberTable){
        #prime_numberが素数の場合、power(2,p)-1を割り切れるか確認
        if((power(2,p)-1) % prime_number == 0){
            # 割り切れたためpower(2,p)-1はメルセンヌ素数ではない
            break
        }
    }
    prime_number += 2p
    # prime_numberを更新
}