[數學]如何快速又準確低算出這題的最大公因數

[數學]如何快速又準確低算出這題的最大公因數

Kahn 於 星期三 七月 23, 2003 3:50 pm


2^20+2^11+1     和     2^19+2^10-1  的最大公因數





除了用手一個一個計算,還有其他簡易的方法嗎

Kahn

 
文章: 101
註冊時間: 2003-06-07
來自: 德國

bugzpodder 於 星期三 七月 30, 2003 11:02 pm


euclid's algorithm.
gcd(2^20+2^11+1,2^19+2^10-1)
=gcd(2^20+2^11+1-(2^19+2^10-1),2^19+2^10-1)
=gcd(2^19+2^10+2,2^19+2^10-1)
=gcd(3,2^19+2^10-1)

since 2^4=1 (mod 3)
then 2^19+2^10-1=2^3+2^2-1 (mod 3)=11 (mod 3)

therefore gcd is 1

bugzpodder

 
文章: 87
註冊時間: 2003-07-30

Raceleader 於 星期三 七月 30, 2003 11:06 pm


Don't collect money

Raceleader
訪客
 

scsnake 於 星期三 七月 30, 2003 11:12 pm


突然想到,在"數學挑戰題"之外的版答對題目,是不是也考慮加錢獎勵?

scsnake
訪客
 

Raceleader 於 星期三 七月 30, 2003 11:14 pm


ㄏㄏㄏ

Raceleader
訪客
 

dick7834 於 星期一 四月 05, 2004 9:16 pm


非常生氣  驚訝  可利用輾轉相除法

dick7834
實習生
實習生
 
文章: 59
註冊時間: 2004-04-04




代數學