2^n+1の形の素数が2もしくはフェルマー素数であることの証明
＊ここで$ n, mは非負整数とする。
フェルマー素数とは、$ 2^{2^n}+1の形の素数である。
$ 2^n+1の形の素数について、以下の式が成り立つ。
$ 2^n+1 = \begin{cases} 2 & (n = 0) \\ 2^{2^m}+1 & (n \ge 1) \end{cases}
以下、$ 2でも$ 2^{2^n}+1でもない$ 2^n+1は合成数になることを示す。
$ 2^{n}+1 = 2^{2^m}+1でなく、かつ$ n \ge 1の場合、非負整数$ a, bを用い$ n = 2^a (2b+1)と表すことができる。
$ \bmod (2^{2^a}+1) で考えると、$ 2^n+1 \equiv 2^{2^a (2b+1)} + 1 \equiv (2^{2^a})^{2b+1} + 1 \equiv (-1)^{2b+1} + 1 \equiv 0 ■
なお、因数分解を使って説明することも可能らしい。
参考