2^n -1 の性質

質問

2 以上の自然数 n について
2^n -1 が n で割り切れない
ことの証明を教えてください。

回答No.2

tmppassenger · ベストアンサー

2 以上の自然数 nで、2^n≡ 1 (mod n)を満たすものがあるとする。明らかにnは偶数ではないので、nは奇数とする。

nを除する素数で最小のものをpとすると、2^n≡1 (mod p)が成り立つ。これは、pを法とする2の位数 ord_p(2)がnを除することを意味する。

＊ 「pを法とする2の位数」とは、「 2^m ≡ 1 (mod p)を満たす最小の正整数m」の事

ところで、Fermatの小定理から、2^(p-1) ≡ 1 (mod p)（pは奇数であることに注意）であるゆえ、 ord_p(2) ≦ p-1であるが、

* nを除する最小の素数がp （つまり、p-1以下の正整数でnを割り切るものは1しかない）
* ord_p(2) は nを除する
* ord_p(2) ≦ p-1

であるから、ord_p(2) = 1となる。つまり 2^1 = 2 ≡ 1 (mod p) となり、これは 2 - 1 = 1をpが除することを意味するが、これは矛盾である。(qed)

お礼

n＞1の最小の約数＞1をp(素数となる)とすると、
modpにおける2の位数ord_p(2)もnの約数だが、
それは最小のはずのpより小さくってしまう、
ということなのですね。
とても分かりやすかったです。有難うございました。

回答No.1

asuncion

2^nは偶数だから2^n - 1は奇数。よって2を素因数として持たない。
したがってnが偶数のとき、2^n - 1はnで割り切れない。

nが奇数のときは、2^nと1がnを法として合同でないことが
言えればよいが、この証明を書くには制限字数が足りないので
識者にお任せします。

お礼

nが偶数の場合、参考になりました。