オイラーの知っていたこと

Fnが素数pを約数に持つなら 　p ≡ 1 (mod 2n+1)　　　　　　　　　　　　…　（＊）

証明）

2^x を f (x) とおくと、（＊）は次のように書きなおされる。

Fn = f (2n) + 1 が素数 p を約数に持つなら 　p ≡ 1 (mod 2n+1)　　　　　　　　　　　　 …　（＊）’

Fnは素数pを約数に持つので

f (2ⁿ) ≡ -1 (mod p)　　　　　　　　　　　　…　（１）

辺々２乗して

{ f (2ⁿ) }² ≡ 1 (mod p)

f (2ⁿ⁺¹) ≡1 (mod p)

ここで位数に関する定理を使う。

位数に関する定理

an ≡ 1 (mod p) 　が成り立つ最小の自然数 n を位数 e と呼び n は常に e の倍数となる。

位数を e とおくと e は 2ⁿ⁺¹ の約数なので

（２^０、２^１、２^２、…、２ⁿ⁺¹）

のどれかになる。ここで

　e = 2^k ( k ≦ n )

とおくと

　f ( 2^k ) ≡ 1 (mod p)　　　　　　　　　　　　…　（２）

両辺に（２）の両辺を掛け合わせる。 …　（３）

　{ f ( 2^k ) }² ≡ 1 (mod p)

　 f ( 2^k+1 ) ≡ 1 (mod p)　

（３）を繰り返すと

f ( 2^k+2 ) ≡ 1 (mod p)

f ( 2^k+3 ) ≡ 1 (mod p)

↓

f ( 2ⁿ ) ≡ 1 (mod p)

これは（１）に反する。

∴ e = 2ⁿ⁺¹（つまり 2ⁿ⁺¹ が位数）

ここでフェルマーの小定理より

フェルマーの小定理

p が素数で a が p の倍数でなければ 　ap-1 ≡ 1(mod p)

2^p-1 ≡ 1(mod p)

p-1 は 2ⁿ⁺¹ の倍数、つまり

p ≡ 1 (mod 2ⁿ⁺¹) （証明終）

　オイラーの知っていたこと