一題國中題目,多種解法

遇過一位提問者發問此題: ( 2^{30} - 1 )31 的倍數嗎?

當然可以使用計算機算出,而個人回答如下:

(1) 利用乘法公式:

(平方差與立方差)

( 2^{30} - 1 ) = ( 2^{15} - 1 )( 2^{15}+1) = ( 2^5 -1 )( 2^{10} + 2^5 +1)(2^{15}+1)

由於 2^5 - 1 = 2 \times 2 \times 2 \times 2 \times 2 - 1 =31 ,故原式為 31 倍數。

(2) 利用 mod

( 2^{30} - 1 ) = (2^5)^6-1=32^6-1

因為 32 除以 31 餘數為 1 ,那麼 32^6 - 1 除以 31 的餘數 等於 1^6 - 1 = 0 ,故原式為 31 倍數。

(3) 利用多項式除法衍生出來的餘式定理

(這是個人想的, 計算量比較小)

2^5 = t, 則 31 = 2^5 - 1 = t - 1 , 2^{30} -1 = t^6 -1 ;
t^6 - 1 除以 t -1 的餘式為 0

這裡當然可以以多項式除法除出餘式為 0 ,不過可利用餘式定理,令 t = 1 ,帶入 t^6 - 1 得餘式為 0 。餘式為 0 ,代表原式為 31 的倍數。

給朋友們參考與指教(其應該能看出來,原式也是 33 的倍數,還有其他數字比較大的)

2 Likes