一個關於最大公因數的問題

Question

請問各位大大2的99次方+1和2的100次方-1的最大公因數是什麼?

Answer 1

愛耍帥同學，你中間的計算過程有點錯誤哦～
第二行的地方，→2^100-1=2(K-1)+1=2K-1
原本是－１，等號後變成＋１了，所以最後應為２Ｋ－３才對

則 Ｋ 與 ２Ｋ－３ 的最大公因數應為３
答：（Ｋ , ２Ｋ－３）＝３.

Answer 2

用輾轉相除法的觀念：2100-1=1*(299+1)+(299-2)299+1=1*(299-2)+3299-2≡(-1)99-2≡-1-2≡-3≡0(mod 3)所以(299-2)可被3整除，亦即兩者的最大公因數是3，所以(2100-1)與(299+1)的最大公因數是3

2005-10-23 21:15:30 補充：
Ｋ與２Ｋ－３的最大公因數為３
沒有這個性質，除非你能確定k是3的倍數，所以愛耍帥同學還是沒有答對，算是矇的。

Answer 3

我們假設 2^99 +1 = K， 則 2^99 = K-1→ 2^100 = 2(K-1)
→ 2^100 -1=2(K-1)-1 = 2K-3
2K-1 與 K用輾轉相除法剩-3
所以 2^99 +1 與 2^100 -1
所以最大公因素為3

Answer 4

~= =~.....請再看一下題目好ㄇ^^.你的做法是2*99+1....不是2的99次方+1~~~之類的

Answer 5

樹同學,你好像看錯題目囉!