数学中国

 找回密码
 注册
搜索
热搜: 活动 交友 discuz
查看: 5694|回复: 10

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

[复制链接]
发表于 2021-7-15 11:52 | 显示全部楼层 |阅读模式


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

本帖子中包含更多资源

您需要 登录 才可以下载或查看,没有帐号?注册

x
发表于 2021-7-15 14:25 | 显示全部楼层
前提知识点
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
回复 支持 反对

使用道具 举报

发表于 2021-7-15 16:07 | 显示全部楼层
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,所有对应因子都是它们的约数,把它们乘起来即可。也就是说,它们的最大公因数与它们指数的分解因式所对应的实际因子乘积相关联。
回复 支持 反对

使用道具 举报

发表于 2021-7-15 16:25 | 显示全部楼层
指数的因子,任意组合就至少对应着一个素数因子。20对应41,4*5*5对应5^3,10对应11,.....
回复 支持 反对

使用道具 举报

发表于 2021-7-15 16:40 | 显示全部楼层
它们两个的指数因子不能构造相同数,则此单因子组合不是它们的共同因子。它们共同指数因子有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.
所以,它们的共同因子取决于指数的最大公约数,所分解因子对应的实际因子的乘积。
回复 支持 反对

使用道具 举报

发表于 2021-7-15 16:45 | 显示全部楼层
证明2^n-2模2^K-1只有k种余数
http://www.mathchina.com/bbs/for ... 6&fromuid=37263
(出处: 数学中国)
有时间,看一看此贴,或许对你有一定的帮助(那都是我自己摸索出来的一点内容),并没有理论上的内容。

点评

我觉得 按照 我上面的2进制表示 很容易怎么这个结论  发表于 2021-7-15 17:03
回复 支持 反对

使用道具 举报

发表于 2021-7-15 17:52 | 显示全部楼层

本帖子中包含更多资源

您需要 登录 才可以下载或查看,没有帐号?注册

x
回复 支持 反对

使用道具 举报

发表于 2021-7-15 20:59 | 显示全部楼层
解:
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
回复 支持 1 反对 0

使用道具 举报

 楼主| 发表于 2021-7-16 09:46 | 显示全部楼层
谢谢各位老师提供不同的方法思路
回复 支持 反对

使用道具 举报

发表于 2021-7-16 10:22 | 显示全部楼层
楼上 kanyikan 的解答很好!已收藏。
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 注册

本版积分规则

Archiver|手机版|小黑屋|数学中国 ( 京ICP备05040119号 )

GMT+8, 2025-7-12 01:47 , Processed in 0.087267 second(s), 17 queries .

Powered by Discuz! X3.4

Copyright © 2001-2020, Tencent Cloud.

快速回复 返回顶部 返回列表