31^17を900で割った時のあまりを求めよ という問題は合同式で解けますか？

31^17を900で割った時のあまりを求めよ

という問題は合同式で解けますか？

No.4 回答者： rnakamra 回答日時： 2020/06/21 19:11

普通に解けます。

31^17=(30+1)^17=Σ[n=0～17] 17Cn 30^n
と2項展開します。
n≧2ついては
30^n≡0(mod 900)
となり、残りの項、30^1と30^0の分だけ計算すればよいのです。

No.3 回答者： sandaba 回答日時： 2020/06/21 16:24

合同式についてはよく知らないのですが、

31^2 = 961 = 900 + 61
ということを使えば解けます。

31^16 = (900 + 61)^8 なので
右辺を展開したとき、900を因数に含まない項は 61^8 のみ、他の項は余りに寄与しない。

で、また同じことをやります。
61^2 = 3721 = (900 * 4) + 121

61^8 = (900 * 4 + 121)^4
右辺を展開したとき、900を因数に含まない項は 121^4 のみ、他の項は余りに寄与しない。

ここでゴリゴリ計算してもいいしもう一回同じことやってもいい。あんまり書いちゃうとつまらないので後は御自分でどうぞ。答えは511。

No.2 回答者： mtrajcp 回答日時： 2020/06/21 16:14

31^2=(30+1)^2=900+2*30+1=61(mod900)

31^2=61^2=(2*30+1)^2=4*900+4*30+1=121(mod900)
31^8=121^2=(4*30+1)^2=16*900+8*30+1=241(mod900)
31^16=241^2=(8*30+1)‭^2‬=64*900+16*30+1=481(mod900)
31^17=481*31=(16*30+1)(30+1)=‬16*900+17*30+1=511(mod900)
∴
511

No.1 回答者： 壊れかけのヒデオ 回答日時： 2020/06/21 16:09

以下法を900とすると、

31^4≡4
31^16≡256
31^17≡8