■フィボナッチとオイラー(その6)

[Q]1000003は素数であるか?

非常に大きい数が素数がどうかを判定するために、オイラーは1から1848までの適切数(便利数)と呼ばれる65個の数を用いた。

1,2,3,4,5,6,7,8,9,10,12,13,15,16,18,21,22,24,25,28,30,33,

37,40,42,45,48,57,58,60,70,72,78.85,88,93,102,105,112,120,

130,133,165,168,177,190,210,232,240,253,273,280,312,330,

345,357,385,408,462,520,760,840,1320,1365,1848...

abが適切数の一つで、n=ax^2+by^2と一意に表され、gcd(ax,by)=1ならばn=p,2p,または2^kである。

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

[A]1000003=19・8^2+3・577^2

57=19・3,gcd(19・3,3・577)=1

よって、1000003は素数

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