求 3^2009 除以 1000 的余数

wintex

請問餘數問題

蔡家雄

3^100  mod  1000 = 1

3^2000  mod  1000 = 1

3^9  mod  1000 = 683

求 3^2009 除以 1000 的余数=683

luyuanhong

题  求 3^2009 除以 1000 的余数。

解  3^2009 = 3×3^2008 = 3×9^1004 = 3×(10-1)^1004

  = 3×[1-C(1004,1)×10+C(1004,2)×10^2-C(1004,3)×10^3+C(1004,4)×10^4- … ]

  其中 -C(1004,3)×10^3+C(1004,4)×10^4- … 中的各项，都是 1000 的倍数，这些项

除以 1000 的余数都是 0 ，所以求 3^2009 除以 1000 的余数时，都可以不考虑。

  C(1004,1)×10 = 1114×10 = 10040 除以 1000 的余数是 40 。

  C(1004,2)×10^2 = 1004×1003×10^2/2 = 50350600 除以 1000 的余数是 600 。

  所以

         3^2009 ≡ 3×[1-C(1004,1)×10+C(1004,2)×10^2]

          ≡ 3×(1-40+600) ≡ 1683 ≡ 683(mod 1000）。

  可见 3^2009 除以 1000 的余数是 683 。

注  一个数只要是 1000 的倍数，除以 1000 的余数必定是 0 ，与这个数的正负无关。

    例如，-3000 除以 1000 的余数是 0 ，-54000 除以 1000 的余数也是 0 。