先日、「2007^19を1044で割った余りを求めよ。」という問題にあいました。
私は2項定理を利用して
2007^19=(1044+963)^19=1044^19+……+963^19

963^19=963*(963*963)^9=963*927369^9=963*927369^9=963*(927072+297)^9
これを繰り返していくと余りは207と出ます。（私は途中で計算の面倒臭さに圧倒されてギブアップしましたが、【数学の部屋】の諸兄が出してくださいました。)

別解として、

1044=2^2×3^2×29
2007=29a+6
2007^2=29b+36=29c+7
2007^4=29d+49=29e-9
2007^8=29f+81=29g-6
2007^16=29h+36=29i+7
2007^19=(29a+6)(29c+7)(29i+7)=29j+4
2007=4k+3
2007^2=4l+1
2007^3=4m+3
・・・
2007^19=4n+3
2007^19=9o
∴2007^19=36p+27
(29+7)p+27=29j+4
7p=29r+6=(28+1)r+6
r=7s+1
よって
7p=29(7s+1)+6=7(29s+5)
p=29s+5
∴2007^19=36p+27=36(29s+5)+27=1044s+207
故に、余りは207

という方法を教えてもらいましたが、もっと簡単に出る方法はないのでしょうか。
別解をご存知でしたら教えてください。どうぞよろしくお願いします。