ベキの法則

質問

ある授業で、ベキの法則を用いた問題があったのですが、機械工学科のためにあまり数学に詳しくなく、この問題が解けなくて悩んでいます。
どなたか、解法を教えてもらえないでしょうか？

因みに問題は、（1056）の22乗(mod2008)です。どなたかよろしくお願いします。

回答No.3

banakona · ベストアンサー

ＡとＢの積は、「ＡをＣで割った余り」と「ＢをＣで割った余り」の積に合同

を使ってみましょう。「合同」はこの場合「Ｃで割った余りが等しい」という意味です。（以下、≡と＝の違いに注意して下さい）

２２を２進数で表すと１０１１０、つまり２＋４＋１６ですから、指数法則により、
（1056）の22乗＝（1056）の2乗×（1056）の４乗×(1056）の１６乗

これら３つを２００８で割った余りをそれぞれ求めて、積を算出すればいい。もし積が２００８以上になったらそれを２００８で割ればいい。

ではやってみましょう。
（1056）の2乗＝１１１５１３６　これを２００８で割ると余りは６９６
　　（1056）の４乗は｛（1056）の2乗｝の2乗なので、６９６の2乗を計算すればいい。
（1056）の４乗≡６９６の2乗＝４８４４１６　これを２００８で割ると余りは４８８
　　（1056）の８乗は使わないけど、次の１６乗を計算するために算出。
（1056）の８乗≡４８８の2乗＝２３８１４４　これを２００８で割ると余りは１２００
（1056）の１６乗≡１２００の2乗＝１４４００００　これを２００８で割ると余りは２６４

以上から
（1056）の22乗＝（1056）の2乗×（1056）の４乗×(1056）の１６乗
　　　　　　　≡６９６×４８８×２６４
　　　　　　　＝８９６６７０７２

これを２００８で割ると余りは１８４０

お礼

ありがとうございます。おかげで何とか理解することができました。

回答No.2

info22

mod(1056^22,2008)=1840
と数学ソフトを使えば一辺に出てきますが、
数学ソフトが使えなければ、根気よく電卓を使って計算して下さい。

1056=1004+x,x=52とおくと
1004xと1004^2 は 2008の倍数だから２項定理で展開すると
1056^22=(1004+x)^22
=x^22 (mod 2008)
=52^22=(52^2)^11
=2704^11=(2008+696)^11
=696^11(mod 2008)
=696*696^10
=696*(696^2)^5
=696*484416^5
=696(2008*241+488)^5
=696*488^5(mod 2008)
=(696*488)*488^4
=339648*(488^2)^2
=(2008*169+296)*238144^2
=296*238144^2(mod 2008)
=296*(2008*118+1200)^2
=296*1200^2(mod 2008)
=296*1440000
=296*(2008*717+264)
=296*264(mod 2008)
=78144
=2008*38+1840
=1840(mod 2008)
=1840

お礼

二項定理で展開する方法もあるのですね。とても参考になりました。

回答No.1

Tacosan

素直に 1056 の 22乗を計算し, それを 2008 で割ったあまりを求めてください. 難しいことはどこにもないはずです.
手元の電卓によると答えは 1840 だそうだ.