■an+b型素数(その9)

  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  (合成数)

===================================