16/05/03 23:48:35.57 +kp+oyUm.net
>>929
nが偶数のときは成立つ。（←分子は奇数）
nが奇数のとき、
2は原始根、2の位数はφ(n)。
nがφ(n)の倍数なら、2^n－1はnの倍数。
しかしnは奇素因数から成り、オイラー関数φ(n)は偶数
なのでnはφ(n)の倍数でない。
2^n－1はnの倍数でない。
〔補題〕
aが原始根のとき、aの位数はφ(n)
a^m≡1 (mod n) ⇔ φ(n)｜m
ここでφ(n)はオイラーのφ関数。
なんか変だな…
16/05/03 23:48:35.57 +kp+oyUm.net
>>929
nが偶数のときは成立つ。（←分子は奇数）
nが奇数のとき、
2は原始根、2の位数はφ(n)。
nがφ(n)の倍数なら、2^n－1はnの倍数。
しかしnは奇素因数から成り、オイラー関数φ(n)は偶数
なのでnはφ(n)の倍数でない。
2^n－1はnの倍数でない。
〔補題〕
aが原始根のとき、aの位数はφ(n)
a^m≡1 (mod n) ⇔ φ(n)｜m
ここでφ(n)はオイラーのφ関数。
なんか変だな…