可利用輾轉相除法
+ / -檢視主題
由 dick7834 於 星期一 四月 05, 2004 9:16 pm
可利用輾轉相除法
由 Raceleader 於 星期三 七月 30, 2003 11:14 pm
由 scsnake 於 星期三 七月 30, 2003 11:12 pm
突然想到，在"數學挑戰題"之外的版答對題目，是不是也考慮加錢獎勵?
由 Raceleader 於 星期三 七月 30, 2003 11:06 pm
Don't collect money
由 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
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
[數學]如何快速又準確低算出這題的最大公因數
由 Kahn 於 星期三 七月 23, 2003 3:50 pm
2^20+2^11+1 和 2^19+2^10-1 的最大公因數
除了用手一個一個計算,還有其他簡易的方法嗎
除了用手一個一個計算,還有其他簡易的方法嗎