证明(1+M+M^2...M^(k1-1))与(1+M+M^2...M^(k2-1))互质 其中k1与k2互质

来源:学生作业学帮网 编辑:学帮网 时间:2024/05/14 19:58:43

证明(1+M+M^2...M^(k1-1))与(1+M+M^2...M^(k2-1))互质 其中k1与k2互质

证明
设k1>k2
设A = (1+M+M^2...M^(k1-1))与B = (1+M+M^2...M^(k2-1))的最大公约数是k
由于
(M-1)A = M^k1 - 1
(M-1)B = M^k2 - 1
所以k能整除M^k1 - 1和M^k2 - 1,所以k不能整除M^k1和M^k2
所以(M-1)(A-B) = M^k1 - M^k2 = M^k2 ( M^(k1-k2) - 1)
所以 k能整除M^(k1-k2) - 1
继续这个步骤,可以得到 k 能整除M-1
或者说M = 1 (mod k)
那么A = 1 + 1 + 1 + ...+ 1 = k1 (mod k)
B = 1 + 1+ ...+1 = k2 (mod k)
而k是A和B的公约数
所以k是k1和k2的公约数,但k1与k2互质
所以k = 1
所以A和B互质