23の23乗を53で割った余りを求めよ。

質問

「23の23乗を53で割った余りを求めよ」

の解き方がわかりません(>_<)

合同式を使って解く問題ですが、
答えの導き方がわかりません。

回答よろしくお願いします!!

回答No.1

Tofu-Yo · ベストアンサー

23^2=529≡52≡-1　(mod53)
を使うとよいかと思います。
23^23=23×(23^2)^11≡23×(-1)^11=-23≡30　(mod53)

もっと簡単なやり方もありそうですが・・・

お礼

分かりやすい回答ありがとうございます!!

助かりましたm(_ _)m

回答No.3

info22_

23^2=529=530-1=10x-1 (x=53とおく)

23^23=23*23^22=23*(23^2)^11
=23(10x-1)^11
２項定理で展開
=23{(10x)^11- … +11(10x)-1}
=23{(10x)^11- … +11(10x)}-23
=[23{(10x)^11- … +11(10x)}-x]+53-23
=[23{(10x)^11- … +11(10x)}-x]+30 (0≦30＜53)

[23{(10x)^11- … +11(10x)}-x]は　x=53 がく繰り出せるので　53の倍数。
従って

　23^23を53で割った余りは 30 である。

[検証]
23^23　-30=20880467999847912034355032910537=[23{(10x)^11- … +11(10x)}-x]
20880467999847912034355032910537/53=[23{(10x)^11- … +11(10x)}-x]/x
=393971094336753057251981753029
で割り切れます。

お礼

回答ありがとうございます!!

こんなやり方もあるんですね...
参考になりました!!

回答No.2

noname#171951

23^2=53×10-1だから
23^2≡-1(mod 53)
となることを使う。

お礼

回答ありがとうございます!!

このやり方を使ってみます。