こんにちは。Inishie Once-in-a-Lifetime Chanceブログのいにしえ時渡です。今回は素因数分解の方法についてです。
2521×2411=6078131を素因数分解したいと思います。まず素数x素数なので、偶数の素数である2を除けば、素数は必ず奇数になります。つまり、素数x素数は奇数x奇数と言えます。
今、一つの素数を2a+1と表して、もう一つの素数を2b+1で表したとします。つまり、(2a+1)x(2b+1)=6078131のaとbについて解くのが素因数分解の一つの方法です。この式を展開すると、4ab+2a+2b+1=6078131であり、2ab+a+b=3039065となります。
今、modという剰余演算を使ってみたいと思います。使い方は1mod2とはある数を2で割った余りが1ということです。例えば、3=1mod2, 7=1mod2, -1=1mod2となります。
2ab+a+b=3039065は左辺の2abは偶数なので2で割った余りは0mod2となります。問題はa+bでありaが奇数でbが奇数なら1+1=0mod2、aが偶数でbが偶数なら0+0=0mod2となります。一方、aが偶数（奇数）であり、bが奇数（偶数）ならば、a+b=1+0=0+1=1mod2となります。
つまり、aとbがそれぞれ2で割られた場合、余りが同じ値なら足して偶数、つまり0mod2になるし、aとbを2で割った余りがそれぞれ異なるならば、余りを足したら奇数つまり1mod2になるということです。
右辺の3039065=1mod2なので、a+b=1mod2となることが分かります。つまりaが奇数（偶数）ならば、bは偶数（奇数）となります。
ここで、a+b=0mod2にしたいので、先の式のaから1を引いてみましょう。つまり,a-1=cとなり、a=c+1を代入します。(2(c+1)+1)x(2b+1)=(2c+3)x(2b+1)=6078131。2cb+b+3c=3039064。
ここで、b+3cはそれぞれ偶数同士か、奇数同士なので、右辺の3039064=0mod2となります。ここで、cbとbとcの係数を足してみます。2+1+3=6です。
3039064mod6をすると4mod6となり、この4を再び3039064から引いてmod(6×2)したものが0mod12なのでaとbはそれぞれ偶数同士であることが分かります。
なぜなら、c=b=0, 2cb+c+b=2x0x0+0+0=0mod12=0mod24。c=b=1, 2x1x1+1+1=6mod12=6mod24となるからです。さらに、c=b=2, 2x2x2+2+2=12mod24, c=b=3, 2x3x3+3+3=0mod24となります。
実際、2c+3=2411,c=1204=0mod2。一方、2b+1=2521, b=1260となります。つまり、c=2d=0mod2, b=2e=0mod2となります。
これをもう2周しましょうか。
cとbにそれぞれ2dと2eを代入すると、(4d+3)x(4e+1)=6078131となります。展開すると、4de+d+3e=1519532となります。1519532=0mod2なので、dとeはd=e=0mod2か、d=e=1mod2となります。
deとdとeの係数は4+1+3=8なので、1519532=4mod8=12mod16。(12-4)mod16=8mod16なので、d=e=1mod2であることが分かります。4d+3=2411, d=602=2f=0mod2であり、4e+1=2521, e=630=2g=0mod2であるので、d=e=1mod2は正しくありません。
次の周は正しくは(8f+3)x(8g+1)=6078131です。展開すると、8fg+f+3g=759766=0mod2です。f=g=0mod2か、f=g=1mod2なので、係数8+1+3=12をします。759766=10mod12=22mod24なので、(22-10)mod24=12mod24となり、f=g=1mod2となります。
実際、f=301=2h+1=1mod2, g=315=2i+1=1mod2となり、正しいことが分かります。もう一周急いでしてみたいと思います。
(16h+11)x(16i+9)=6078131。16fg+9f+11g=379877=1mod2。j=i-1。i=j+1。(16h+11)x(16j+25)=6078131。16hj+25h+11j=379866。
h+j=0mod2。16+25+11=52。379866=6mod52=58mod104。(58-6)=52mod104。h+j=1mod2。h=150=0mod2 ,j=156=0mod2で正しくない。
ここで、先程正しくなかった(16h+11)x(16i+9)=6078131で、k=h-1, h=k+1。(16k+27)x(16i+9)=6078131。16ik+27i+9k=379868=0mod2。
i+k=0mod2。16+27+9=52。8mod52=60mod104。(60-8)=52mod104。i=k=1mod2。16k+27=2411, k=149=1mod2。16i+9=2521,i=157=1mod2。よって正しい。
(4d+3)x(4e+1)=6078131。d=s+2,e=t+2。(4s+11)x(4t+9)=6078131。4st+9s+11t=1519508。4+9+11=24。1519508=20mod24=20mod48。(20-20)mod48=0mod48。s=t=0mod2。s=600=0mod2。t=628=0mod2。
検算することが大事なようだ。
コメント