求正整数 2^120-1 与 2^100-1 的最大公因数

Bathan_Tam

请问代数问题的方法 (不用计算机)

lihp2020

前提知识点
1 辗转相除求最大公约数 gdb（A ,B） = gdb(A,B-nA)
其中 其中 B-nA >0 n只正整数
2 2^N-1  在二进制中 就是N个1

现在 求的是 二进制(120个1 与100个1的最大公约数)  

120个1 =100个1 *2的20次方 + 20个1

辗转相除 就变成（20个1 与100个1的最大公约数)
结果就是20个1

100个1 =20个1 *2的80次方+20个1 *2的60次方+20个1 *2的40次方+20个1 *2的20次方+20个1 *2的0次方

其中 **个1  表示一个数的的二进制  里面2进制个10进制混用 有点难看
20个1 = 2^20-1

独舟星海

120的分解因式：2*2*2*3*5,100的分解因式：2*2*5*5，它们的实际因子2对应3,2*3对应9,4对应5,4*5对应25,3对应7,5对应31；10对应11，所有对应因子都是它们的约数，把它们乘起来即可。也就是说，它们的最大公因数与它们指数的分解因式所对应的实际因子乘积相关联。

独舟星海

指数的因子，任意组合就至少对应着一个素数因子。20对应41,4*5*5对应5^3,10对应11，.....

独舟星海

它们两个的指数因子不能构造相同数，则此单因子组合不是它们的共同因子。它们共同指数因子有2,4,5,10,20，
120/100=6/5，最大公约数为：20,20的所有因子组合为：20,10,5,4,2，然后2对应3,4对应5,5对应31,10对应11,20对应（4*5）25，另外20对应41，所以最终它们的共同因子：3*5*31*11*5*41=1048575.
所以，它们的共同因子取决于指数的最大公约数，所分解因子对应的实际因子的乘积。

白新岭

证明2^n-2模2^K-1只有k种余数
http://www.mathchina.com/bbs/for ... 6&fromuid=37263
(出处: 数学中国)
有时间，看一看此贴，或许对你有一定的帮助（那都是我自己摸索出来的一点内容），并没有理论上的内容。

lihp2020

kanyikan

解：
2^120-1=(2^20)^6-1
2^100-1=(2^20)^5-1
记a=2^20
2^120-1=a^6-1=(a-1)(a^5+a^4+a^3+a^2+a+1)
2^100-1=a^5-1=(a-1)(a^4+a^3+a^2+a+1)
所以gcd(2^120-1,2^100-1)=(a-1)gcd(a^5+a^4+a^3+a^2+a+1,a^4+a^3+a^2+a+1)
而
gcd(a^5+a^4+a^3+a^2+a+1,a^4+a^3+a^2+a+1)
=gcd(a^4+a^3+a^2+a+1,1)
=1
所以gcd(2^120-1,2^100-1)=(a-1)=2^20-1

Bathan_Tam

谢谢各位老师提供不同的方法思路

luyuanhong

楼上 kanyikan 的解答很好！已收藏。