質問＜１５７８＞２００４／２／６
from=受験生
「今年の大学の問題」

２９の３３乗を９００で割った余りは？

お便り２００４／２／６
from=Tetsuya Kobayashi

29 = 30 - 1
900 = 30^2
を利用して、二項式展開により、
(30-1)^33 = (900の倍数) + 33*30 - 1
よって余りは 89 。

お便り２００４／２／６
from=こんにちは

29^33＝(30－1)^33

二項定理で展開すると

(30－1)^33
＝∑_[i=0,33](33_C_i)(30)^i*(-1)^(33-i)
＝∑_[i=2,33](33_C_i)(30)^i*(-1)^(33-i)+33*30-1

i≧2のとき(30)^iは900＝(30)^2で割り切れる
よって、
∑_[i=2,33](33_C_i)(30)^i*(-1)^(33-i)+33*30-1
＝900*(整数)+989
＝900*{(整数)+1}+89

よって29^33を900で割った余りは89である。

お便り２００４／２／６
from=wakky

29の33乗を900で割った余りということですが、
29^33＝(30-1)^33です。
また900=30^2です。
このあたりに着目して、二項定理を利用してみます。
29^33=(30-1)^33
=33_C_0*30^33+33_C_1*30^32(-1)+33_C_2*30^31(-1)^2+.....
　......+33_C_31*30^2(-1)^32+33_C_32*30(-1)^32+33_C_33*(-1)^33
(30^2でくくって)
30^2{33_C_0*30^31+33_C_1*30^30(-1)+33_C_2*30^29(-1)^2+.....
　......+33_C_31*(-1)^31}+33_C_32*30(-1)^32+33_C_33*(-1)^33
30^2{          }の部分は900で割り切れます。
つまり残りの33_C_32*30(-1)^32+33_C_33*(-1)^33を計算してみると
33*30*(-1)^32-1=990-1=989
これを900で割ると余りは89となります。