數學求餘數 (1)－dlxpxv7的部落格

標題:

數學求餘數 (1)

發問:

求 22^(33^(44^55)) 除以 120 的餘數。

最佳解答:

考慮 2^33^44??, 注意由 23 開始每隔四次方出現循環: 23 ≡ 8 (mod 120) , 2? ≡ 16 (mod 120) , 2? ≡ 32 (mod 120) , 2? ≡ 64 (mod 120) , 2?≡ 8 (mod 120) , .... 而 33^44?? ≡ (4×7 + 1)^44?? ≡ 1 (mod 4) , 令 33^44?? = 4n + 1 , 則 2^33^44?? ≡ 2???1 ≡ 32 (mod 120)。另一方面, 112 ≡ 1 (mod 120) , 令 33^44?? = 2k + 1 , 則 11^33^44?? ≡ 112??1 ≡ 11(112)? ≡ 11(1)? ≡ 11 (mod 120)。從而 22^33^44?? ≡ 2^33^44?? × 11^33^44?? ≡ 32 × 11 ≡ 112 (mod 120)。答 : 2^33^44?? 除以 120 的餘數是 112 。 2015-05-13 20:04:20 補充：看到 22 , 不知何解就有把它拆成 2 × 11 的衝動......