初等数论关于最大公因数的证明
a,b是两个正整数，证明(2^a-1,2^b-1)=2^r-1.其中r=(a,b)求助啊求助啊！！！...
a,b是两个正整数，证明(2^a-1,2^b-1)=2^r-1.其中r=(a,b)
求助啊求助啊！！！ 展开
求助啊求助啊！！！ 展开
1个回答
展开全部
由Bezout定理, 存在正整数u, v使ua-vb = (a,b) = r.
设d = (2^a-1,2^b-1), 则d | 2^b-1 | 2^(vb)-1, 进而有d | 2^(vb+r)-2^r = 2^(ua)-2^r.
又d | 2^a-1 | 2^(ua)-1, 相减得d | 2^r-1.
反过来, 由r | a有2^r-1 | 2^a-1, 同理2^r-1 | 2^b-1, 故2^r-1 | d.
于是(2^a-1,2^b-1) = d = 2^r-1.
设d = (2^a-1,2^b-1), 则d | 2^b-1 | 2^(vb)-1, 进而有d | 2^(vb+r)-2^r = 2^(ua)-2^r.
又d | 2^a-1 | 2^(ua)-1, 相减得d | 2^r-1.
反过来, 由r | a有2^r-1 | 2^a-1, 同理2^r-1 | 2^b-1, 故2^r-1 | d.
于是(2^a-1,2^b-1) = d = 2^r-1.
本回答由提问者推荐
已赞过
已踩过<
评论
收起
你对这个回答的评价是？
推荐律师服务：
若未解决您的问题，请您详细描述您的问题，通过百度律临进行免费专业咨询
