91學測數學選填第14題詳解

設 $2^{20}-1$ 與 $2^{19}+1$ 的最大公因數為 $d$，即 $d = \gcd(2^{20}-1, 2^{19}+1)$。 利用輾轉相除法（或整除性質）： $$2^{20}-1 = 2(2^{19}+1) - 3$$ 因此，$d$ 必須能整除 $(2^{20}-1) - 2(2^{19}+1) = -3$。因為最大公因數為正數，所以 $d$ 只能是 $1$ 或 $3$。 接著檢驗 $2^{19}+1$ 是否能被 $3$ 整除： 因為 $2$ 的冪次除以 $3$ 的餘數呈現 $2,1,2,1,\ldots$ 的循環，且 $19$ 為奇數，所以 $2^{19}$ 除以 $3$ 餘 $2$。 因此 $2^{19}+1$ 是 $3$ 的倍數。 同理，$20$ 為偶數，所以 $2^{20}$ 除以 $3$ 餘 $1$，因此 $2^{20}-1$ 也是 $3$ 的倍數。 因此，它們的最大公因數為 $3$。