どなたか、至急お願いします！！！！！！1001^4+2002^4+3003^4+4004^4を5で割

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

No.3 ベストアンサー 回答者： ありものがたり 回答日時： 2021/05/30 20:10

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 でよかったか。

この回答へのお礼

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

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

No.2 回答者： cruelman 回答日時： 2021/05/30 15:57

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

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

No.1 回答者： raizo-ichikawa 回答日時： 2021/05/30 15:51

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

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


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