题目

初等数论关于最大公因数的证明
a,b是两个正整数,证明(2^a-1,2^b-1)=2^r-1.其中r=(a,b)

提问时间：2021-02-26

答案

由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.