作业帮 > 数学 > 作业

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

来源:学生作业帮 编辑:神马作文网作业帮 分类:数学作业 时间:2024/11/06 10:52:27
证明(1+M+M^2...M^(k1-1))与(1+M+M^2...M^(k2-1))互质 其中k1与k2互质
证明(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互质
再问: 继续这个步骤,可以得到 k 能整除M-1 什么意思 为什么k1-k2-k2……会变成1啊
再答: k能整除M^k1-1,并且能整除M^k2-1所以 k能整除M^(k1-k2) - 1 继续这个步骤,可以得到 k 能整除M^(k1 % k2) -1设k1 % k2 = r那么k能整除M^r - 1所以k能整除M^(k2 % r)-1由于(k1,k2) = 1那么最后必然可以得到余数1所以k能整除M - 1 这个是欧几里德算法(辗转相除法) k | (M-1)所以M = 1 (mod k)所以M^i = 1 (mod k)所以A = k1 (mod k)B = k2 (mod k)
再问: 大神留下qq把 以后有问题好找你
再答: 275070089