・高次の因数分解                        GAI 氏

 高次元ではこんなことが起こっていた!

x2-1=(x-1)(x+1) 、x3-1=(x-1)(x2+x+1) 、x4-1=(x-1)(x+1)(x2+1) 、x5-1=(x-1)(x4+x3+x2+x+1)

・・・・・・・・・・・・・・・・・・など、馴染みの因数分解では、係数がすべて 1、−1、0 のいずれか
になり、これは未来永劫 xn-1 も同様だと思いこんでいた。ところが、n=105 になった時

x105-1=(-1+x) (1+x+x2) (1+x+x2+x3+x4) (1+x+x2+x3+x4+x5+x6) (1-x+x3-x4+x5-x7+x8)
     (1-x+x3-x4+x6-x8+x9-x11+x12) (1-x+x5-x6+x7-x8+x10-x11+x12-x13+x14-x16+x17-x18+x19
     -x23+x24) (1+x+x2-x5-x6-2x7-x8-x9+x12+x13+x14+x15+x16+x17-x20-x22-x24-x26-x28+x31
     +x32+x33+x34+x35+x36-x39-x40-2x41-x42-x43+x46+x47+x48)

が起こり、始めて係数に−2が出現した。これを契機に更に2が出るnを探してみた。すると、
n=165、195、210、255、・・・・でも、2、−2などが係数として出現することがわかった。

 更に、n=385 にさしかかったら、

x385-1=(-1+x) (1+x+x2+x3+x4) (1+x+x2+x3+x4+x5+x6) (1+x+x2+x3+x4+x5+x6+x7+x8+x9+x10)
     (1-x+x5-x6+x7-x8+x10-x11+x12-x13+x14-x16+x17-x18+x19-x23+x24)(1-x+x5-x6
     +x10-x12+x15-x17+x20-x23+x25-x28+x30-x34+x35-x39+x40)(1-x+x7-x8+x11-x12
     +x14-x15+x18-x19+x21-x23+x25-x26+x28-x30+x32-x34+x35-x37+x39-x41+x42-x45
     +x46-x48+x49-x52+x53-x59+x60) (1+x+x2+x3+x4-x7-x8-x9-x10-2 x11-x12-x13-x14
     -x5+x18+x19+x20+x21+x22+x35+x36+x37+x38+x39-x42-x43-x44-x45-2 x46-x47-x48
     -x49-x50+x53+x54+2 x55+2 x56+2 x57+x58+x59-x62-x63-x64-x65-2 x66-x67-x68
     -x69+x71+x72+2 x73+2 x74+x75+x76+x77-x81-x82-x83-2 x84-2 x85-x86-x87-x88
     +x90+x91+x92+x93+x94+x95+x96-x100-2 x101-x102-x103-x104+x106+x107+2 x108
     +2 x109+2 x110+2 x111+2 x112+x113+x114-x116-2 x117-2 x118-3 x119-3 x120
     -3 x121-2 x122-2 x123-x124+x126+x127+2 x128+2 x129+2 x130+2 x131+2 x132
     +x133+x134-x136-x137-x138-2 x139-x140+x144+x145+x146+x147+x148+x149+x150
     -x152-x153-x154-2 x155-2 x156-x157-x158-x159+x163+x164+x165+2 x166+2 x167
     +x168+x169-x171-x172-x173-2 x174-x175-x176-x177-x178+x181+x182+2 x183
     +2 x184+2 x185+x186+x187-x190-x191-x192-x193-2 x194-x195-x196-x197-x198
     +x201+x202+x203+x204+x205+x218+x219+x220+x221+x222-x225-x226-x227-x228
     -2 x229-x230-x231-x232-x233+x236+x237+x238+x239+x240)

となり、なんと今度は係数3 (絶対値で判断)が出現した。(他にも、n=595、665、770、935、
1155、・・・・でも出現する)こうして更なる係数の更新(絶対値でみる)をめざして進んでいくと

 n=1365 で係数4 、n=1785 で係数5

が始めて出現し出した。ここで、整数列大辞典で検索をかけて調べてみると、「A013594」に
行き着き、なんとそこには、xn-1 の因数分解式の中に係数 i が始めて現れることになるn(i)
の調査が既になされており、

 n(2)=105 (始めて係数に2が出現するのは、x105-1である)

 n(3)=385 (始めて係数に3が出現するのは、x385-1である)

 n(4)=1365

  ・・・・・

と続き、なんとn(1000)までの表がついていた。ちなみに、n(1000)=285285 即ち、x285285-1
を因数分解すると、式の中に1000の係数を含む式が含まれていることを示す。

 さらに、この285285での最高係数を別途計算機で調べてみたら、1182の係数まで含まれ
ていることがわかりました。この整数列大辞典を見る度に、世界中の誰かがとんでもない世
界までも既に詳しく調べ尽くしていることに驚いてしまいます。


(コメント) 上記の話題に関連する問題が、数学セミナー’14 3月号の「エレガントな解答
      をもとむ」に出題されている。(平成26年2月12日付け)

問 題  2013−12015−1 を因数分解すると、どちらも係数に0、±1以外をもつ多項式
     を含む。一般に、奇数をベキ指数にもつ多項式 x−1 を整数係数の多項式に因数
     分解するとき、その因数の係数に、0、±1以外をもつ多項式を含むような整数の組
     n、n+2で最小のものを見つけよ。



 うんざりはちべえさんからのコメントです。(平成26年2月11日付け)

 GAIさんの xn-1 の因数分解ですが、これは円分多項式というそうです。

  xn-1=(x-1){xn-1+・・・+x3+x2+x+1}

とする分は、1以外ありませんが、{xn-1+・・・+x3+x2+x+1}を因数分解するとそういうことになり
ます。それで、わたしは、{xn-1+・・・+x3+x2+x+1}の利用についてはなるべく、因数分解を注意
しています。

 たとえば、1が偶数個並んだ数は、11で割れます。

1111111111111111=11x101010101010101=11x101x1000100010001=11x101x10001x100000001

 したがって、 x15+x14+x13+・・・+x3+x2+x+1=(x+1)(x2+1)(x4+1)(x8+1) とすれば、1以上の数は
出て来ません。

 1が3の倍数個並んだ数は、111、つまり、x2+x+1で割れます。1が素数の倍数個はすべて
同じようにすれば、1以外を出さずに因数分解できます。(それが正しい因数分解であるとは
言えませんけれど。)


 GAI さんからのコメントです。(平成26年2月11日付け)

 x8+x7+1 、x8+x6+1 、x8+x5+1 、x8+x4+1 、x8+x3+1 、x8+x2+1 、x8+x+1 の因数分解の方
法の見分け方は可能ですか?


 うんざりはちべえさんからのコメントです。(平成26年2月11日付け)

 上記は、1が並んだ数の場合の特殊な例です。maximaで因数分解してみました。

 x8+x7+1=(x2 + x + 1) (x6 - x4 + x3 - x + 1) 、x8+x6+1 既約、x8+x5+1 既約

 x8+x4+1=(x2 - x + 1) (x2 + x + 1) (x4 - x2 + 1) 、x8+x3+1 既約、x8+x2+1 既約

 x8+x+1= (x2 + x + 1) (x6 - x5 + x3 - x2 + 1)

 しかし、ぜんぜん面白みが無いですよね。マイナスがあったりして、きれいな式じゃないで
すよね。円分多項式もきれいな式じゃないですよね、マイナスがあったり、1でない係数があ
ったりして。

 x進数同士の掛け算というふうにするには、マイナスがあったら、x進数では係数が0、1で
なくなって、汎用な式ではなくなってしまいますよね。

 (2x+1)(3x2+4x+1)=21x341 となれば、係数が4なので、これは5進数以上でないと汎用に
なりませんよね。もちろん、答えは進数によって変わってしまいます。

 (2x+1)(3x2-x+1) となると、xの係数はx-1で3は2になって、汎用ではないですよね。

 (x+1)(x2+1)=11x101=1111 で進数は2以上なので、どの進数でも成り立つ掛け算ですよね。


 DD++さんからのコメントです。(平成26年2月11日付け)

 係数が1ばかりであるxの多項式の因数分解について、項数kがある素数pの倍数であり、
各項のベキをpで割った余りとして0からp-1まで同じ個数ずつ出てくる場合は

   xp-1+xp-2+……+x+1

を因数に持つはずです。証明は難しくないので略します。

 x8+xk+1の場合は、項数3で、8(mod 3)=2と0(mod 3)=0 が既にあるので、k mod3=1のとき
すなわち、k=1、4、7のとき、x2+x+1が因数になりますね。もっとも、それを括り出しただけで因
数分解が完了するかどうかが別問題であることは、k=4 の場合を考えれば明らかですが..。

 係数付きの場合は剰余の個数に係数の重みをつけて計算すれば同じようにできるはずで
す。

 x8+2x7+x5+x3+1 の場合は項数6と考えてベキを3で割った余りが、0、1、2それぞれ2個ずつ
なので、x2+x+1が因数として出てくるはず、とか。

 p、qを素数として、xpq-1は項数0と考えて、xp-1+xp-2+……+x+1とxq-1+xq-2+……+x+1を因
数に持つはず、とか。

 x105-1やx385-1でも同様の結果になっていることが、冒頭のGAIさんによる実際の因数分解
結果で確認できます。xk-1で、kの素因数が3種類以上になると、これらですぐに見つかる因
数3つと因数定理から見つかるx-1の計4回の割り算の結果で、係数が±1でなくなる何かが
起こるのだろうという気がしていますが、はてさて...。


 うんざりはちべえさんからのコメントです。(平成26年2月11日付け)

 x8+x4+1は、100010001 そこで、1が並んだ数にするには、

      11101110=10x 1110111=10x111x 10001

 1が並んだ数は、 111111111=111x 1001001

よって、111x1001001-10x111x10001=111x(1001001-10x10001)=111x(1001001-100010)

より、 x8+x4+1=(x2+x+1)(x6-x5+x3-x+1)


(コメント) 面白い因数分解の方法ですね!


 うんざりはちべえさんからのコメントです。(平成26年2月12日付け)

 DD++さん、私の計算では、 x7+x2+1=(x2 + x + 1) (x5 - x4 + x2 - x + 1)

 これは、111(=x2 + x + 1)で、1が8つだと、11(=x+1)でしか割れないのでできません。もうひ
とつ項を増やすと、
            x7+x5+x2+1=(x + 1) (x2 + 1) (x4 - x3 + x2 - x + 1)

 これは、x+1があるので、うまく行きます。ところが、1が9つのこの式では、111(=x2 + x + 1)
でないとまずいのですが、
                x8+x5+x+1=(x + 1) (x7 - x6 + x5 + 1)

ご覧のとおり、11(=x+1)です。これは、DD++さんのおっしゃってることで説明ができますか?
私には、ご説明がちょっと難しかったです。まあ、引き算があるからこんなことになるんで、1
が並んだ数ならうまくいくんですがねぇ....。


 DD++さんからのコメントです。(平成26年2月13日付け)

 うんざりはちべえさんの計算の核を今ひとつ掴みきれていないのですが、私が言っている
ことをはちべえさん風の計算に(そういう意味なのだろうという推測の元で)翻訳するとこうい
うことですね。

 100010001の因数を探すのに以下のような方法を取ります。

 まず、1の個数は、3個です。これを、3桁ずつ区切り、足し算すると、 100+010+001=111
と、全て1になったので、111という因数があるとわかります。
(全て同じ数になれば別にそれが1でなくとも構いません。)

 x7+x2+1 つまり、10000101の場合は、1の個数が3と数えて、10+000+101=111 なので、111
は因数です。最高位がどの桁にあるかではなくて1がいくつあるかに着目するのがミソですね。

 x7+x5+x2+1 つまり、10100101の場合は、1の個数が4と数えて、その素因数2を使って、
10+10+01+01=22 と、全て2が並ぶので、11は因数です。

 ついでに、22桁ごとに区切っても、1111になるので、1を2桁ごとに2個並べた101も因数です。
(もし別の式で仮に23桁ごとで同様にできれば、1を22桁ごとに2個並べた10001も因数、以下
同様)

 x8+x5+x+1の因数が、x2+x+1でなく、x+1であることはぜひご自身で確かめてみてください。

 実は、これは係数に1以外がある場合にも使えて、120101001の場合は、桁の合計6の素因
数である3桁で区切って、120+101+001=222 なので、111は因数(2桁ずつは42になってしまう
ので失敗)とか、x15-1 つまり、100000000000000[-1]([-1]はそういう一文字の数字と思う)は、
桁の合計0が任意の素数を約数に持ち、全て同じ数が並ぶのは、1と[-1]が同じ桁位置で足し
合わされる3桁か5桁区切り、つまり、111と11111が因数とか、5x3+8x2+7x+4 すなわち、5874
だと、58+74=[12][12] となるので、11、すなわち、x+1が因数とか(これも[12]はそういう一文字
の数字と思う)。繰り上がりや繰り下がりを認めない変わりに、各桁表記に負数などを認める
特殊な数表記法を考えることで、大きな係数や負係数のものでも対応できます。

 注意事項を2つ述べますと、まず1つはこれで見つけた因数が全てとは限らないこと(例えば
100010001はこの方法では完全な因数分解はできません)、もう1つは普通の十進法の因数
分解でこれをやろうとすると繰り上がりの関係で見逃す場合があること(十進法209の素因数
11を見つけようと思うと方法に少し補正が必要です)。

 こんな感じで解答になってますでしょうか?


 うんざりはちべえさんからのコメントです。(平成26年2月13日付け)

 DD++さん、適切な大変わかり易い説明で助かりました。ありがとうございました。

 私のは、 x8+x4+1=x8+x7+x6+x5+x4+x3+x2+x+1-(x7+x6+x5+x3+x2+x) をやっていたのです。
すなわち、 100010001=111111111-011101110 において、111111111=111x1001001 と、111
で割れることがわかり、 また、011101110=111x100010=111x10x10001 より、111で割れるこ
とがわかります。だから、

100010001=111111111-011101110=111x1001001-111x10x10001=111x(1001001-10x10001)

となるわけですね。だから、1を並べる数によって決まりがあるわけです。

 例えば、DD++さんの説明から、x7+x2+1 は111で割れるから、1を9個並べれば良いと思い
ました。 111111111-010000101=101111010 となるわけですが、これはDD++さんのでは、

  101+111+010=222 で、111 いいのですが、私のではダメです。

 (x8+x6+x5+x4+x3+x)/(x2+x+1)=x6 - x5 + x4 + x3 - x2 + x と、確かに111で割れています。

 101111010=111x1911910 ( 9は-1のつもり) ですから、

 111111111-101111010
=111x1001001-111x(1911910)=111x(1001001-1911910)=111x(190191)

すなわち、 (x2+x+1)(x5-x4+x2-x+1)=x7+x2+1 ですから、たまたま、うまく行ったのでしょうね。


 DD++さんからのコメントです。(平成26年2月14日付け)

 なるほど、1が繋がってないと困るから0が繋がっている部分を 1-1 と見做すことで、1の9
連続から1の3連続を2箇所引く形にしたわけですか。それで、9と3と3の公約数が3だから、
111で割り切れると。

 しかし、これは確かに0と1を不規則に並べられると(つまり次数が不規則に並んでいると)
苦しいかもしれませんね。

 0になっている部分の埋め方をこんな風に工夫すれば対応できなくもないですが...。

例: x7+x2+1の場合、つまり、10000101の場合、10000101+1111110-11111100=111だから、
   以下略。(積み算だとずれそうなので横に書きました、すみません。)

 この式だけ見ると何でこうなったのかわかりにくいかもしれませんが、10000に1110を足し
て11100を引くとこの1を右に3桁ずらせる、というような計算を2セット使って、7乗の桁を1乗
の桁に無理やりずらして111を作っています。
(これを手抜きで計算して因数になるかどうかだけの判断に使っているのが私のやり方です)

 もちろん、2桁ずらし等もできますが、1が3箇所である以上いい結果が出る可能性は皆無、
試してみる価値がありません。

 価値がないといえば、この手法自体がせめて係数は1だけだけど次数は飛んでる因数くら
いは見つけられないと「なんとなく面白い話」以上の価値がなさそうな。

 例えば、x6+x4+x3+x2+x+1の因数x2+1とかは、同じような方法でうまく見つけられないもので
しょうか。欲を言えば、係数-1を許容した形のものも。もし、そこまでできたら大元の「xk-1を
因数分解したときに係数に2以上が出てくることがある」話もいろいろ見えてきそうですが。


 空舟さんからのコメントです。(平成26年2月14日付け)

【命題】 f(x) を多項式、nを自然数とする。xの次数をnで割った余りがkであるような項の係
     数の和がk=0、1、2、・・・、n-1 に対して、kによらない一定値になるならば、f(x) は、
     1+x+x2+・・・+xn-1 を因数にもつ

【説明】 g(x) = 1+x+x2+・・・+xn-1 = 0 は重解を持たないことを既知とする。g(a) = 0 を満たす
     a に対して、f(a)=0 が成り立つことを示せば良い。

     (1-x)g(x) = 1-xn に注意すれば、a = 1 を得る。このことは、 aZn+k = ak を意味する。

    従って、(xの次数をnで割った余りがkであるような項全体)に、x=a を代入したものは、

        (xの次数をnで割った余りがkであるような項全体の係数の和)・ak

    に一致する。従って、条件に仮定された「kによらない一定値」をAとすれば、

      f(a) = A(1+a+a2+・・・+an-1)

    が成り立つが、右辺の括弧の因数は、g(a)に一致するので、これは 0 である。

     よって、示された。

(g(x)が重解を持たないことの補足)

 G(x) = (1-x)g(x) = 1-xn = 0 が重解を持たないことを示せば良い。G’(x) = nxn-1 = 0 の解
は、x=0 だけであることから分かります。


 うんざりはちべえさんからのコメントです。(平成26年2月14日付け)

 空舟様、フォローありがとうございます。

 DD++さんの「例えば、x6+x4+x3+x2+x+1の因数x2+1とかは、・・・」から、以下のようなことに
気づきました。

 1010+0101=1111=101x11 、 100100+010010+001001=111111=1001x111

  10001000+01000100+00100010+00010001=11111111=10001x1111

  1000010000+0100001000+0010000100+0001000010+0000100001=1111111111=100001x11111

とでもなるわけですね。だから、

    101001010+101=101001111=101x1000011

とでもなるわけですね。なるほど。思いもよりませんでした。


 攻略法さんからのコメントです。(平成26年2月15日付け)

 「例えば、x6+x4+x3+x2+x+1の因数x2+1とかは、同じような方法でうまく見つけられないもので
しょうか。
」について、除数 x2+1 の係数のパターンに着目して、

  0x3+1x2+0x+1より、 (01)(01)  ※01が2つ並ぶ

 被除数の係数を、 (x7  x6)    (x5  x4)
             (x3  x2)    (x    1 )
と並べて、
        (0 1) (0 1)
      + (1 1) (1 1)
      ---------------
        (1 2) (1 2)

 x8+x7+1 については、因数 x2+x+1 と仮定して、(1)(1)(1)

 被除数の係数を、 (x8)  (x7)  (x6)
             (x5)  (x4)  (x3)
             (x2)  (x1)  (x0)
と並べて、
       (1) (1) (0)
       (0) (0) (0)
       (0) (0) (1)
      --------------
       (1) (1) (1)

 x8+x4+1、x8+x+1 も同様。

                                         投稿一覧に戻る