gooドクター有料プランが1ヶ月間無料!

どなたか、至急お願いします!!!!!!1001^4+2002^4+3003^4+4004^4を5で割った余りを求めよ。また、7^7001を48て割った余りを求めよ。と言う問題で手が止まってしまっています。modを使って教えて頂きたいです。

A 回答 (3件)

1001^4+2002^4+3003^4+4004^4 程度なら、


mod を表立って使わんでも
1001^4 + 2002^4 + 3003^4 + 4004^4
= (1000+1)^4・{ 1 + 2^4 + 3^4 + 4^4 }
= { 1000(1000^3 + 4・1000^2 + 6・1000 + 4) + 1 }{ 1 + 16 + 81 + 256 }
= 5・200(1000^3 + 4・1000^2 + 6・1000 + 4)・354 + (5・70 + 4)
= 5{ 200(1000^3 + 4・1000^2 + 6・1000 + 4)・354 + 70 } + 4
くらいの計算でも示せるけどね。

mod 5 を使えば、
1001^4 + 2002^4 + 3003^4 + 4004^4
≡ 1^4 + 2^4 + 3^4 + 4^4
= 1 + 16 + 81 + 256
≡ 1 + 1 + 1 + 1
= 4.
こっちのほうが手軽か。

7^7001 を mod 48 で計算するなら、オイラーの定理がいいかと。
素因数分解 48 = (2^4)・3 よりオイラー関数の値が
φ(48) = 48(1 - 1/2)(1 - 1/3) = 16 だから、
7001 ≡ 9 mod 16 より 7^7001 ≡ 7^9 mod 48.
7^9 = 7^(2・4+1) = (7^2)^4・7 = 49^4・7 ≡ 1^4・7 = 7 mod 48.

ああ、どうせ 7^2 ≡ 1 mod 48 を使うなら、直接
7^7001 = 7^(2・500+1) = 49^500・7 ≡ 1^500・7 でよかったか。
    • good
    • 0
この回答へのお礼

とてもわかりやすく、理解できました!ありがとうございました!!

お礼日時:2021/05/31 07:02

7の2乗=49を48で割れば余り1です。

これを利用すれば7の7001乗を7で割った余りも求められるでしょう。
    • good
    • 0

100以上は割り切れるから、


(1^4+2^4+3^4+4^4)÷5を計算して余りを求めればよろし。


7^7001を48て割った余りは分からんです。
    • good
    • 0

お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!

このQ&Aを見た人はこんなQ&Aも見ています


このQ&Aを見た人がよく見るQ&A

人気Q&Aランキング