整数の割り算

質問

以下の画像にある値は、載っている問題集の解答によると136とありましたが途中経過が書かれていません。手元でゴリゴリ計算したところ130になりました。以下のサイトではやはり130になりました。
http://www.wolframalpha.com/input/?i=mod%28%28%2812371^56%2B34%29^28%29%2C243%29
自分の計算に自信がありません。12371^56≡2^28(mod 243)から始めて7^56から順次累乗の中身を243で割っていくやり方でやりました。結果の検証と、もし243が3^5であることが使えるとか何か簡単に計算する方法があればお願いします。

回答No.2

tmpname · ベストアンサー

それを考えると、
2 = 3-1だから
2^28 = (3-1)^28で、
mod 3^5のあまりを考えると結局第0項と第1項しか残らず、
(3-1)^28≡ {(-1)^28 + 28 * 3 * (-1)^27} (mod 3^5)
≡ -83 ≡ 160 (mod 3^5)
とした方が早いですね...

お礼

たしかに、これだとずいぶん簡単ですね。
誤植があってかえって勉強になりました。
ありがとうございました。

回答No.1

tmpname

確かに130にしかなりませんね。ruby 2.2.3でやってもpython 2.7.10でやっても130ですし、手元で計算しても130にしかなりませんから130でしょう。

私はこうしました。最後の方で243 = 3^5であることを使います。
12371 ≡ -22 mod 243
12371 ^ 2 ≡ 22^2 ≡ -2 mod 243
12371 ^ 56 ≡ 2^28 mod 243

2^8 = 256≡ 13 mod 243
2^16 ≡ 169 ≡ -74 mod 243
2^24 ≡ 13 * (-74) ≡ 10 mod 243
2^28 ≡ 160 mod 243

160 + 34 = 194 ≡ -49
≡ - (3^3 + 2 * 3^2 + 3 + 1) mod 3^5
よって(12371^56 + 34)^28 ≡ (3^3 + 2 * 3^2 + 3 + 1)^28 mod 3^5

ここで、(a + b + c + d)^n の所謂「一般項」は (a^x)(b^y)(c^z)(d^w) n! / (x! y! z! w!) （但しx + y + z + w = n）で今の場合 a= 3^3, b = 2*3^2, ... n=28として、「一般項」の中に3のべきが4以下になるものを探すと、案外数が少ない
＊例えば、a = 3^3の所のべきは、0か1しか取れない
＊ n! / (x! y! z! w!) のところで、約分していく途中分子に 28-1 =27 = 3^3というかなり3のべきの大きい数字が残る事が多く、この事も 「一般項」のなかの3のべきを押し上げる

で、結局
(x, y, z, w) =
(0, 0, 0, 28)
(0, 0, 1, 27)
(0, 1, 0, 27)
(1, 0, 0, 27)
の場合しか結局残らず、

(3^3 + 2 * 3^2 + 3 + 1)^28 ≡ 1 + 3*28 + 2*3^2 * 28 + 3^3 * 28
= 1345 ≡ 130 mod 243