二項定理を使うな

• http://q.hatena.ne.jp/1152432833

目的は、(y+2)^10 を y^3 で割ったあまりの式を出すこと。二項定理で展開しちゃうのは知ってる人には手っ取り早い方法だけど、それを知らない人に対してどうするかという視点では、答えられていないのが興味深い。

自分的には、方程式レベルでべたに一こづつ展開していきゃいいだけじゃないだろうかと思う。この項の係数法則を定理にしたのが、二項定理ではあるんだけど直接定理を使わなければいいのではないかと思う。

(y+2)^2 = y^2 + 2y
              + 2y + 2 * 2
        = y^2 + 2(2)y + 2^2

(y+2)^3 = y^3 + 2(2)y^2 + (2^2)y
              + 2y^2    + 2(2^2)y + 2^3
        = y^3 + 3(2)y^2 + 3(2^2)y + 2^3 

(y+2)^4 = y^4 + 3(2)y^3 + 3(2^2)y^2 + 2^3y
              + 2y^3    + 3(2^2)y^2 + 3(2^3)y + 2^4
        = y^4 + 4(2)y^3 + 6(2^2)y^2 + 4(2^3)y + 2^4

剰余を求める場合、途中で式の構成要素を割った剰余で計算して剰余を求めても同じ結果になる（コンピュータではとても重要な性質だけど、これは習うんだっけ）。そこで途中ですべて剰余にしてしまう

(y+2)^2 % y^3 = y^2 + 2(2)y + 2^2         ・・・ ①
(y+2)^3 % y^3 = 3(2)y^2 + 3(2^2)y + 2^3   ・・・ ②
(y+2)^4 % y^3 = 6(2^2)y^2 + 4(2^3)y + 2^4

(y+2)^5 % y^3 = ① * ② % y^3
              = ( ((...) + 3(2^3)y^2) % y^3 
                 +((...) + 6(2^3)y^2 + 3(2^4)y) % y^3
                 +((...) + 2^3y^2    + 2(2^4)y + 2^5) % y^3) % y^3
              = ( 3(2^3)y^2
                + 6(2^3)y^2 + 3(2^4)y
                + 2^3y^2    + 2(2^4)y + 2^5 ) % y^3
              = (10(2^3)y^2 + 5(2^4)y + 2^5) % y^3
              =  10(2^3)y^2 + 5(2^4)y + 2^5   ・・・③

(y+2)^10 % y^3 = ③ * ③ % y^3
               = ( ((...) + 10(2^8)y^2) % y^3
                 + ((...) + 25(2^8)y^2 + 5(2^9)y) % y^3
                 + ((...) + 10(2^8)y^2 + 5(2^9)y + 2^10) % y^3) % y^3
               = ( 10(2^8)y^2
                 + 25(2^8)y^2 + 5(2^9)y
                 + 10(2^8)y^2 + 5(2^9)y + 2^10) % y^3
               = (45(2^8)y^2 + 10(2^9)y + 2^10) % y^3
               = 45(2^8)y^2 + 10(2^9)y + 2^10

とまあ二項演算の結果と同じになるわけだ。