Re: [中學] 請問一題餘數問題

[mack (腦海裡依然記得妳)]

※ 引述《terry617 (魔數師)》之銘言：
: 最近在書上看到一題~
: 不確定是哪個範圍~
: 請各位高手幫忙解嚕~
: 25^60 除以 216 的餘數是多少?
: 請問答案及算法~ 感謝~
           120         120               120       120       120
(x-1)^120=C   x^120 - C   x^119 + ... - C   x^3 + C   x^2 - C    x + 1
           120         119               3         2         1
                       120       120
         = x^3*Q(x) + C   x^2 - C    x + 1
                       2         1
令x=6
                       120       120
(6-1)^120= 6^3*Q(x) + C   6^2 - C    6 + 1
                       2         1

餘數 = (120*119/2)*6^2 - 120*6 + 1 (mod 216)
     = 7140*36 - 720 + 1 (mod 216)
     = 12*36 - 720 + 1 (mod 216)
     = 432 - 720 + 1 (mod 216)
     = -287 (mod 216)
     = 145 (mod 216)

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 125.224.48.241