初等数论关于最大公因数的证明
a,b是两个正整数,证明(2^a-1,2^b-1)=2^r-1.其中r=(a,b)
人气:480 ℃ 时间:2020-05-19 02:47:46
解答
由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.
推荐
- 求初等数论证明:
- 初等数论证明题
- 一道初等数论证明题
- 初等数论中有关最大公因数的问题:25a+b=125,d=(a,a+b),则d等于多少?如果(a,5)=1则d等于多少?
- a与b是互质数,它们的最大公因数是(),他们的最小公倍数是().要说明原因
- 买钢笔用去我钱数的1/3,买故事书用去4元,这时用去的钱数与剩下钱数比是5:4.你知道剩下多少钱吗?
- 甲班的图书本数比乙班多80本,甲班的图书本数是乙班的3倍,甲班和乙班各有图书多少本?
- 与冒意思接近的词有哪些
猜你喜欢
- 已知19900乘5乘72乘35乘75乘(),要使这个连乘积的没尾连续有6个0,括号里至少填多少?
- 水文特征,水系特征分别包括哪些要素?
- 英语中有一单选题:It____Saturday tomorrow.A.will be B.is C.is going to D.is going该选哪一答案?
- 13的因数都是质数吗?
- 爱莲说中写莲为什么还提到了菊和牡丹,有什么作用
- do,like,don't,you,I,sandwich,no(连词成句)
- 蒲公英的生长过程 ( ) 、( )、( ) 、( )、( ).每个括号里写两个字.
- 一项工程单独做,甲要15天完成,乙要30天完成,开始二人一起干,因工作需要甲中途调走,结果乙一共用了16天完成.甲队工作了几天?