■1000009は素数であるか?
5525=74^2+7^2=70^2+25^2=62^2+41^2
=50^2+55^2=22^2+71^2=14^2+73^2
など合成数では多くの2平方和分解が生じる.
実際,2平方和分解が少なくとも2通り見つかったら,その数は素数ではないことになる.
[Q]1000009は素数であるか?
===================================
[A]1000009=1000^2+3^2=972^2+235^2 →No.
フィボナッチの恒等式
(a^2+b^2)(c^2+d^2)=(ac+bd)^2+(ad−bc)^2
(a^2+b^2)(c^2+d^2)=(ac−bd)^2+(ad+bc)^2
より,
ac+bd=1000,ad−bc=±3
ac−bd=972, ad+bc=235
bd=14, bc=119
b=7,d=2,c=17
17a+14=1000→a=58
a^2+b^2=3413,c^2+d^2=293
1000009=293・3413 (合成数)
===================================