附注 1: 两个数 a 和 b 除以 s 同余, 记为 a = b (mod s). 而且对任何非负的整数 k, 同余式 a^k = b^k (mod s) 也成立
附注 2: 已知 a^m 和 a^n 的某个性质,利用 (a^m)^n = (a^n)^m 是数学常用技巧。 怎么没想起来呢?
命题:m 是正奇数, n 是正整数, 则 GCD(2^m-1, 2^n+1)=1
证明: 设 s = GCD(2^m-1, 2^n+1).
则 2^m = 1 (mod s), 2^n = -1 (mod s).
于是 2^(m*n) = (2^m)^n = 1^n = 1 (mod s)
2^(m*n) = (2^n)^m = (-1)^m = -1 (mod s) (因为 m 是奇数 )
所以 1 = -1 (mod s), 即 s | 1-(-1), 即 s | 2
于是 s = 1 或 2. 但 s 不能等于 2, 所以 s = 1. 证毕
附注 2: 已知 a^m 和 a^n 的某个性质,利用 (a^m)^n = (a^n)^m 是数学常用技巧。 怎么没想起来呢?
命题:m 是正奇数, n 是正整数, 则 GCD(2^m-1, 2^n+1)=1
证明: 设 s = GCD(2^m-1, 2^n+1).
则 2^m = 1 (mod s), 2^n = -1 (mod s).
于是 2^(m*n) = (2^m)^n = 1^n = 1 (mod s)
2^(m*n) = (2^n)^m = (-1)^m = -1 (mod s) (因为 m 是奇数 )
所以 1 = -1 (mod s), 即 s | 1-(-1), 即 s | 2
于是 s = 1 或 2. 但 s 不能等于 2, 所以 s = 1. 证毕
锟斤拷锟洁辑时锟斤拷: 2023-08-31 20:13:17