數學問題:2的20次方-1和2的19次方+1的最大公因數

已邀请:

海马非马

赞同来自:

变量声明和初始化
$a=2^{20}-1$
$b=2^{19}+1$

求最大公约数的阿基米德算法(这里相减就达到了求余数的效果)
let $a=a-b=2^{20}-2^{19}-2=2^{19}-2$;
let $b=b-a=2^{19}+1-\left(2^{19}-2\right)=3$

现在看a(值为$2^{19}-2$)除以3的余数:

一般的,$2^n$除3的余数
n 余数
1 2
2 1
3 2
4 1
...

观察发现2的奇次方除3余数为2,偶次方除2余数为1,所以$2^{19}$除3余数为2,$2^{19}-2$(当前a的值)除3余数是0,从而3是题中所求两数的最大公约数。

一般的,对足够大的整数k, $2^{k+1}-1$和$2^k+1$的最大公约数用上面的方法
a = $2^{k+1}-1$
b = $2^k+1$

let a=a-b=$2^k-2$
let b=b-a=3
如果k为奇数,公因数是3,如果k是偶数,公因数是1。

要回复问题请先登录注册