附注 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. 证毕

锟斤拷锟洁辑时锟斤拷: 2023-08-31 20:13:17