- 830 名前：Kummer ◆g2BU0D6YN2 [2007/03/04(日) 11:02:16 ]
- 補題
n ≧ 3 を有理整数とする。
5^(2^(n-3)) ≡ 1 + 2^(n-1) (mod 2^n)
である。
証明
n に関する帰納法を使う。
n = 3 のときは正しい。
ある n ≧ 3 に対して
5^(2^(n-3)) ≡ 1 + 2^(n-1) (mod 2^n)
が正しいとする。
>>829 より、
5^(2^(n-2)) ≡ (1 + 2^(n-1))^2 (mod 2^(n+1))
ここで
(1 + 2^(n-1))^2 = 1 + 2^n + 2^(2n - 2)
2n - 2 ≧ n + 1
だから
5^(2^(n-2)) ≡ 1 + 2^n (mod 2^(n+1))
証明終
