MENU
159,181

スレッドNo.121

因数分解

N0=110001011
N1=11111111
N2=11112121
N3=133113133
N4=14141441
N5=15151515115
N6=11611661
N7=17171111
N8=1811811818
N9=191111911
は手計算で因数分解できるものなのか?

引用して返信編集・削除(未編集)

とりあえず瞬殺できるものから。

N1 = 11111111 = 1111*10001 = 11*101*10001
さて、GAI さんがこれで終わるだけの面白みのない問題を出すとは思えないので、10001 は合成数、それもそこそこ大きな素数の積だと信じることにします。

10001 を 2 つの自然数の積で書くと考えると、その相乗平均は √10001 で 100 よりわずかに大きい数です。
また、10001 は 4 で割ると 1 余る数なので、これが 2 つの数の積であるならばそれは 4 で割ると 1 余る数同士の積か、あるいは 4 で割ると 3 余る数同士の積。
つまり、その 2 つの数の和は 4 で割ると 2 余ります。
これら 2 つの情報に、どちらもそこそこ大きな素因数という情報を追加すると、2 数の相加平均は 100 より少し大きい奇数であるとわかります。
ということで、これを 101+2k と書くことにします。

すると 2 つの数を解に持つ二次方程式は
x^2 - 2(101+2k)x + 10001 = 0
となり、その判別式は
D/4 = (101+2k)^2 - 10001 = 4k^2 + 404k + 200 = 4(k^2+101k+50)
あとはこの括弧内が平方数になるような k の値を小さい順に試しながら探せばよく、
k=1 のとき 152 は平方数ではない
k=2 のとき 256 は平方数
とすぐにみつかります。

2 数の相加平均が 105 ということは和は 210 で、積が 10001 なのですから、差は
√(210^2-4*10001) = √4096 = 64
つまり 2 数は 105 + 32 = 137 と 105 - 32 = 73

以上より、N1 = 11111111 = 11*73*101*137

引用して返信編集・削除(未編集)

同じやり方でもう 1 つ。
N2 = 11112121 = 11111111+1010
と考えると、N1 の結果と合わせてこれが 101 の倍数であることは明らかで、
N2 = 11112121 = 101*110021

開平法を使って頑張れば √110021≒331.7 で、ということは 2 数の相加平均は 331 より少し大きい奇数なので 331+2k とおいて、同様に進めて、
D/4 = (331+2k)^2 - 110021 = 4(k^2+331k-115)
この括弧内が平方数になる k を探します。

k=1 のとき 217 は平方数ではない
k=2 のとき 551 は平方数ではない
k=3 のとき 887 は平方数ではない
k=4 のとき 1225 は平方数

2 数の相加平均が 339 で、和が 678、積が 110021 なので、差は
√(678^2-4*110021) = √19600 = 140
つまり 2 数は 339 + 70 = 409 と 339 - 70 = 269

以上より N2 = 11112121 = 101*269*409
一応 19 以下の素数で割ってみて、これが全部素数と確認して終了。

引用して返信編集・削除(未編集)

N7 もいけるかと思いましたが、170011 の処理がこの方法では無理そうですね。
2 つの数がおそらく倍以上差があるようで、この方法ではちょっと厳しい。
さあどうしようかな。

引用して返信編集・削除(未編集)

f(k)=(412+2k)^2-170011とすると
f(k)=4k^2+1648k-267
kが偶数のときf(k)≡5(mod8)となるが
mod8での平方剰余は0,1,4だけなので平方数にならない。
k=2m-1とするとf(k)=g(m)=16m^2+3280m-1911
m≡0,1,2,3,4,5,6,7,8に対してg(m)≡6,8,6,0,8,3,3,8,0(mod9)だが
mod9での平方剰余は0,1,4,7だけなので
平方数になる可能性があるのはm≡3,8(mod9)のときのみ。
m≡3(mod9)のときm=9t-6とおくと
g(m)=h(t)=1296t^2+27792t-21015
h(1)=8073, h(2)=39753は一の位が3なので平方数ではない。
h(3)=74025が平方数ならば27^2=729,28^2=784からh(3)=275^2でなければ
ならないが、275^2=75625なのでh(3)は平方数ではない。
h(4)=110889が平方数ならば33^2=1089,34^2=1156から
h(4)=333^2または337^2でなければならないが、333^2=110889なので
h(4)は平方数。
(たまたま見つかったのでm≡8(mod9)は考える必要がなくなった)
t=4→m=30→k=59→412+2k=530なので
170011=530^2-333^2とわかる。以下略。

引用して返信編集・削除(未編集)

このスレッドに返信

このスレッドへの返信は締め切られています。

ロケットBBS

Page Top