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