|
|
問題
123456789を因数分解せよ。
類題
□□□□□×□□□□□=123456789
考察
フェルマー法
n=x^2-y^2=(x-y)(x+y)
X=[√n]として、順にx=X+1,X+2,X+3,…で、x^2-nを満たす平方数y^2を求める。
このとき、x+y,x-yがnの因数となる。
（終わり）
答え 筆算による
11111×11111=123454321（[√n]に相当する）なので、x+1=11112である。
x=11112のとき、11112×11112=123476544
123476544
- 123456789
-----------
5) 19755 ←5の倍数判定より
-------
3951
これは、5の倍数でないので、5^2を因数に持たない。これより、平方数にならない。
補足
11112×11112は直接計算してよいが、
x^2と(x+1)^2=x^2+2x+1の関係より、123454321+2×11111+1=123476544と計算できる。
（終わり）
x=11113のとき、11113×11113=123498769
123498769
- 123456789
-----------
5) 41980 ←5の倍数判定より
-------
8396
これは、5の倍数でないので、5^2を因数に持たない。これより、平方数にならない。
x=11114のとき、11114×11114=123520996
123520996
- 123456789
-----------
11) 64207 ←2,3,5,7で割り切れないので
-------
5837
これは、11の倍数でないので、11^2を因数に持たない。これより、平方数にならない。
x=11115のとき、11115×11115=123543225
123543225
- 123456789
-----------
2) 86436
-------
2) 43218
-------
3) 21609
-------
3) 7203
-------
7) 2401
-------
7) 343
-------
7) 49
-------
7
これより、y=86436=(2×3×7×7)^2=294^2
よって、11115-294=10821、11115+294=11409から、123456789=10821×11409
3の倍数の判定より、10821=3×3607、11409=3×3803から、123456789=3^2×3607×3803
続いて、3607,3803が素数であろことを判定する。
試し割り法
k^2≦mを満たす素数kがmを割り切らないことを確認する。
m=3607のとき、k=3,5,7,…,59で割り切らない。
m=3803のとき、k=3,5,7,…,61で割り切らない。
以上より、求めることができた。
（終わり）
平方数の判定は、√キー付き電卓があると楽ですね。
LET N=123456789
LET X=INT(SQR(N))
DO
LET X=X+1
LET Y2=X*X-N
LET Y=INT(SQR(Y2))
PRINT X;Y2;Y
LOOP UNTIL Y^2=Y2
PRINT X-Y;X+Y
END
実行結果
11112 19755 140
11113 41980 204
11114 64207 253
11115 86436 294
10821 11409
|
|