Perfect 19-powers in Fibonacci Sequence

[2004.02.14]Fibonacci数列に現れる完全19乗数

Fibonacci数列に現れる完全19乗数を求めるプログラム(pari/gp)

■J.McLaughlinは、参考文献[1]で、小さい素数p=5,7,11,13,17について、Fibonacci数列中の完全p-乗数は、自明なもの(0,1)に限ることを証明している。

ここでは、次の素数19に対して、Fibonacci数列に現れる完全19乗数は、0,1に限ることを、J.McLaughlinの方法で証明する。

詳細は、参考文献[1]を参照のこと。

Fibonacci数列を{F_m : m >= 0}とする。

また、[1]の中で、Peth\"oは、
     F_m=x^qならば、q < 10⁹⁸である
ことを言明した(1981)と、記述されている。

■初等的考察
-----------------------------------------------------------------
[Lemma 1(Peth\"o, 1983)]
q >= 3を正整数とする。
ある正整数xに対してF_m=x^qであれば、
     m=0,1,2,6
または、
     ある素数pとある正整数x₁が存在して、p|mかつF_p=x₁^q
となる。
-----------------------------------------------------------------

Lemma 1より、mとして、奇素数のみを考えれば良いことが分かる。

一般に、任意のm >= 0に対して、
     F_m+1²-F_m+1F_m-F_m² = (-1)^m
であることは容易に分かる。

F_m=x¹⁹, F_m+1=yと仮定する。
mは奇数なので、
     y²-yx¹⁹-x³⁸+1 = 0
を得る。
yの２次式の判別式は平方数であるので、ある正整数zに対して、
     5x³⁸-4 = z²
となる。
z² ≡ 1 (mod 5)なので、z≡±1(mod 5)、つまり、ある整数vに対して、z = 5v±1である。よって、
     x³⁸ = (2v)²+(v±1)²
を得る。
ここで、(x,v)=1は直ちに分かる。また、xは奇数で、vは偶数であることも分かる。
[
仮に、vが奇数であると仮定する。
2vと(v±1)は偶数であるので、xは偶数である。
よって、
     x³⁸ ≡ 0 (mod 16)
である。しかし、v≡1,3,5,7,11,13,15 (mod 16)のそれぞれに対して、
     (2v)²+(v±1)² ≡ 4, 8 (mod 16)
であるので、矛盾する。
]
よって、UFDである整数環 Z[sqrt{-1}]上の素因数分解を考えることにより、
v±1+2v*sqrt{-1}はZ[sqrt{-1}]の19乗数であり、ある有理整数A,B₁に対して、
     v±1+2v*sqrt{-1} = (A+B₁*sqrt{-1})¹⁹
となる。
ここで、Aは奇数であり、B₁は偶数であることも簡単に分かる。
B₁=2Bとすると、Bは整数であり、少しの計算により、
     ±1 = B¹⁹Σ_j=0⁸(-1)^j2^2j(C(19,2j)*(A/B)^19-2j-C(19,2j+1)*(A/B)^19-2j-1)
を得る。
この19次Thue方程式の整数解(A,B)を求めれば良い。
ここで、C(m,n)={m!}/{n!*(m-n)!}である。

     f₁₉(x) = Σ_j=0⁸(-1)^j2^2j(C(19,2j)*x^19-2j-C(19,2j+1)*x^19-2j-1)
         = x¹⁹ - 19x¹⁸ - 684x¹⁷ + 3876x¹⁶ + 62016x¹⁵ - 186048x¹⁴ - 1736448x¹³ + 3224832x¹² + 19348992x¹¹ - 23648768x¹⁰ - 94595072x⁹ + 77395968x⁸ + 206389248x⁷ - 111132672x⁶ - 190513152x⁵ + 63504384x⁴ + 63504384x³ - 11206656x² - 4980736x + 262144

とすると、f₁₉(x)はQ上で既約であり、その根θ₁,...,θ₁₉は全て実数である。

これらの根の１つをθ_i[以下では、添字iを省略して単にθと書くこともある]とすると、
     ±1 = Π_k=1¹⁹(A-θ_kB)= Norm_K/Q(A-θ_iB)
を得る。ただし、K=Q(θ_i)である。

(A-θ_iB)は、代数体Q(θ_i)の単数である。
Q(θ_i)の単数群のrankは18である。その基本単数をε₁⁽ⁱ⁾,...,ε₁₈⁽ⁱ⁾とし、β_i=A-θ_iBとする。
よって、整数u₁,...,u₁₈が存在して、
     β_i = ±Π_k=1¹⁸ε_k^(i)u_k
となる。

U=max_1<=k<=18|u_k|とする。
Uの上限を求めれば良い。

[pari/gpによる計算]

gp>  read("fibo.gp")
time = 660 ms.
gp>  nf=bnfinit(f(19,x));
time = 1mn, 26,936 ms.
gp>  for(i=1,18,print("e_",i,"=",nf.fu[i]))
e_1=1347/1073741824*x^17 - 25593/1073741824*x^16 - 230031/268435456*x^15 + 1299429/268435456*x^14 + 5168715/67108864*x^13 - 15367713/67108864*x^12 - 35372539/16777216*x^11 + 64381177/16777216*x^10 + 93772629/4194304*x^9 - 109808847/4194304*x^8 - 103144653/1048576*x^7 + 76916655/1048576*x^6 + 44571225/262144*x^5 - 19301739/262144*x^4 - 5832681/65536*x^3 + 1115699/65536*x^2 + 41569/4096*x - 6715/4096
e_2=2911/8589934592*x^18 - 56869/8589934592*x^17 - 245081/1073741824*x^16 + 770859/536870912*x^15 + 5434967/268435456*x^14 - 2479643/33554432*x^13 - 36832953/67108864*x^12 + 46539227/33554432*x^11 + 48769727/8388608*x^10 - 186727417/16777216*x^9 - 109439447/4194304*x^8 + 84329001/2097152*x^7 + 50743889/1048576*x^6 - 16671127/262144*x^5 - 7989939/262144*x^4 + 4959473/131072*x^3 + 179285/131072*x^2 - 584449/131072*x + 679/4096
e_3=115/1073741824*x^18 - 2299/1073741824*x^17 - 38181/536870912*x^16 + 8141/16777216*x^15 + 206359/33554432*x^14 - 434909/16777216*x^13 - 167193/1048576*x^12 + 521845/1048576*x^11 + 1639225/1048576*x^10 - 8330217/2097152*x^9 - 6437129/1048576*x^8 + 892787/65536*x^7 + 1175825/131072*x^6 - 1261061/65536*x^5 - 44421/16384*x^4 + 36227/4096*x^3 - 22119/16384*x^2 - 2091/16384*x + 255/8192
e_4=41157/8589934592*x^18 - 778921/8589934592*x^17 - 14103481/4294967296*x^16 + 9836459/536870912*x^15 + 20018917/67108864*x^14 - 29136295/33554432*x^13 - 561406863/67108864*x^12 + 496315187/33554432*x^11 + 1564076553/16777216*x^10 - 1774500061/16777216*x^9 - 3805779499/8388608*x^8 + 696314233/2097152*x^7 + 127284655/131072*x^6 - 114078491/262144*x^5 - 220611663/262144*x^4 + 23730889/131072*x^3 + 30727761/131072*x^2 + 156715/131072*x - 669177/65536
e_5=6561/2147483648*x^18 - 234009/4294967296*x^17 - 9248823/4294967296*x^16 + 626211/67108864*x^15 + 26899371/134217728*x^14 - 22476285/67108864*x^13 - 382596453/67108864*x^12 + 6745599/2097152*x^11 + 528551163/8388608*x^10 + 8426889/8388608*x^9 - 2426740749/8388608*x^8 - 26050617/262144*x^7 + 273002877/524288*x^6 + 69106791/262144*x^5 - 74421645/262144*x^4 - 136757/1024*x^3 + 342803/8192*x^2 + 898783/65536*x - 45927/65536
e_6=5669/4294967296*x^18 - 50243/2147483648*x^17 - 4006523/4294967296*x^16 + 527541/134217728*x^15 + 11678381/134217728*x^14 - 283453/2097152*x^13 - 166326913/67108864*x^12 + 9311229/8388608*x^11 + 57443329/2097152*x^10 + 15447721/4194304*x^9 - 1053104953/8388608*x^8 - 30894777/524288*x^7 + 118175359/524288*x^6 + 9499725/65536*x^5 - 32492169/262144*x^4 - 2461081/32768*x^3 + 1395867/65536*x^2 + 206153/32768*x - 24171/65536
e_7=153/67108864*x^18 - 189651/4294967296*x^17 - 6628279/4294967296*x^16 + 1262353/134217728*x^15 + 18521721/134217728*x^14 - 31852917/67108864*x^13 - 254490793/67108864*x^12 + 73046799/8388608*x^11 + 345472823/8388608*x^10 - 569054201/8388608*x^9 - 1630146101/8388608*x^8 + 122806151/524288*x^7 + 211937151/524288*x^6 - 89646421/262144*x^5 - 92511065/262144*x^4 + 5808681/32768*x^3 + 3744961/32768*x^2 - 1620371/65536*x - 493399/65536
e_8=1437/4294967296*x^18 - 13787/2147483648*x^17 - 975907/4294967296*x^16 + 357439/268435456*x^15 + 5426171/268435456*x^14 - 4317733/67108864*x^13 - 18234927/33554432*x^12 + 18380691/16777216*x^11 + 93428389/16777216*x^10 - 3899857/524288*x^9 - 190106131/8388608*x^8 + 20295981/1048576*x^7 + 31513681/1048576*x^6 - 3654715/262144*x^5 + 26983/4096*x^4 - 38399/65536*x^3 - 768471/32768*x^2 - 168533/32768*x + 22081/65536
e_9=6265/2147483648*x^18 - 226785/4294967296*x^17 - 8777999/4294967296*x^16 + 636281/67108864*x^15 + 25498103/134217728*x^14 - 25139435/67108864*x^13 - 365708913/67108864*x^12 + 19465879/4194304*x^11 + 519316467/8388608*x^10 - 131320323/8388608*x^9 - 2549782125/8388608*x^8 - 8092701/262144*x^7 + 334628041/524288*x^6 + 52221157/262144*x^5 - 130479217/262144*x^4 - 3311051/16384*x^3 + 661801/8192*x^2 + 1260671/65536*x - 79887/65536
e_10=56047/8589934592*x^18 - 1080943/8589934592*x^17 - 19018477/4294967296*x^16 + 14270167/536870912*x^15 + 106799515/268435456*x^14 - 89396849/67108864*x^13 - 369910539/33554432*x^12 + 818200703/33554432*x^11 + 1018042919/8388608*x^10 - 3219023767/16777216*x^9 - 4903519733/8388608*x^8 + 1446422717/2097152*x^7 + 1306292981/1048576*x^6 - 148218121/131072*x^5 - 70832123/65536*x^4 + 104286669/131072*x^3 + 36752917/131072*x^2 - 24913611/131072*x + 674911/65536
e_11=2089/4294967296*x^18 - 38729/4294967296*x^17 - 724683/2147483648*x^16 + 58443/33554432*x^15 + 8424825/268435456*x^14 - 5271171/67108864*x^13 - 61621631/67108864*x^12 + 2664457/2097152*x^11 + 184888087/16777216*x^10 - 72889483/8388608*x^9 - 127770801/2097152*x^8 + 3558267/131072*x^7 + 169807731/1048576*x^6 - 10801187/262144*x^5 - 52955193/262144*x^4 + 255605/8192*x^3 + 1654805/16384*x^2 - 605321/65536*x - 307713/32768
e_12=3009/2147483648*x^18 - 57631/2147483648*x^17 - 512191/536870912*x^16 + 186947/33554432*x^15 + 1440525/16777216*x^14 - 4573889/16777216*x^13 - 19925571/8388608*x^12 + 20212657/4194304*x^11 + 108781645/4194304*x^10 - 150593867/4194304*x^9 - 128202029/1048576*x^8 + 7705187/65536*x^7 + 8123269/32768*x^6 - 1317865/8192*x^5 - 6263851/32768*x^4 + 1202109/16384*x^3 + 1200237/32768*x^2 - 114691/32768*x + 593/8192
e_13=2461/8589934592*x^18 - 58697/8589934592*x^17 - 730589/4294967296*x^16 + 555985/268435456*x^15 + 856167/67108864*x^14 - 18988379/134217728*x^13 - 18399651/67108864*x^12 + 57488987/16777216*x^11 + 35401289/16777216*x^10 - 586883699/16777216*x^9 - 59206759/8388608*x^8 + 166419807/1048576*x^7 + 1279719/65536*x^6 - 158615475/524288*x^5 - 8712243/262144*x^4 + 13454821/65536*x^3 + 20473/131072*x^2 - 5297689/131072*x + 455299/65536
e_14=16451/8589934592*x^18 - 313655/8589934592*x^17 - 5616195/4294967296*x^16 + 504075/67108864*x^15 + 3969925/33554432*x^14 - 48955439/134217728*x^13 - 221723273/67108864*x^12 + 54012879/8388608*x^11 + 615100443/16777216*x^10 - 818631697/16777216*x^9 - 1491324113/8388608*x^8 + 22342557/131072*x^7 + 99588703/262144*x^6 - 146528139/524288*x^5 - 85747249/262144*x^4 + 6601807/32768*x^3 + 10282495/131072*x^2 - 5743935/131072*x + 127565/65536
e_15=3187/4294967296*x^18 - 64171/4294967296*x^17 - 1054777/2147483648*x^16 + 1849081/536870912*x^15 + 5706273/134217728*x^14 - 25255583/134217728*x^13 - 4666055/4194304*x^12 + 125027877/33554432*x^11 + 5863641/524288*x^10 - 130134373/4194304*x^9 - 194728421/4194304*x^8 + 234045499/2097152*x^7 + 40575671/524288*x^6 - 82742793/524288*x^5 - 3151733/65536*x^4 + 7898663/131072*x^3 + 1026941/65536*x^2 - 122737/65536*x - 13813/32768
e_16=2863/4294967296*x^18 - 28001/2147483648*x^17 - 1928905/4294967296*x^16 + 1527159/536870912*x^15 + 5376855/134217728*x^14 - 19918771/134217728*x^13 - 73975487/67108864*x^12 + 96106595/33554432*x^11 + 3158061/262144*x^10 - 203420553/8388608*x^9 - 481038027/8388608*x^8 + 202523269/2097152*x^7 + 61927397/524288*x^6 - 94581377/524288*x^5 - 23878703/262144*x^4 + 18654177/131072*x^3 + 1124601/65536*x^2 - 591953/16384*x - 4201/65536
e_17=5475/8589934592*x^18 - 100049/8589934592*x^17 - 477073/1073741824*x^16 + 1152017/536870912*x^15 + 11007349/268435456*x^14 - 5937195/67108864*x^13 - 78084335/67108864*x^12 + 40243065/33554432*x^11 + 27245241/2097152*x^10 - 93252601/16777216*x^9 - 260077397/4194304*x^8 + 10034907/2097152*x^7 + 130651195/1048576*x^6 + 1832279/131072*x^5 - 24542229/262144*x^4 - 1987397/131072*x^3 + 2961581/131072*x^2 + 558891/131072*x - 1227/8192
e_18=53385/8589934592*x^18 - 1038907/8589934592*x^17 - 562983/134217728*x^16 + 13962907/536870912*x^15 + 25029815/67108864*x^14 - 88946293/67108864*x^13 - 340215005/33554432*x^12 + 824882227/33554432*x^11 + 1807957105/16777216*x^10 - 3260577315/16777216*x^9 - 1018644613/2097152*x^8 + 1442316553/2097152*x^7 + 119010627/131072*x^6 - 137948701/131072*x^5 - 77478063/131072*x^4 + 77034121/131072*x^3 + 7509037/131072*x^2 - 7457415/131072*x - 14195/8192
time = 54 ms.

■Uの最初の上限を計算する。
jを|β_j|=min_1<=i<=19|β_i|を満たすものとする。jは予め分からないので、j=1,...,19のそれぞれの場合に対して(並行して)議論する。

定数c₁,c₂,c_2a,c₃,c₄,c₅,c₆,c₇,K₁,K₂,K₃,C₀を以下のように定義する。

     c₁ = min{ |θ_j-θ_i| : 1 <= i <= 19, i != j },
     c₂ = max{ |θ_t-θ_r|/|θ_t-θ_s| : 1 <= r,s,t <= 19, r != s != t != r },
     c_2a = max{ |θ_j-θ_s|/|θ_j-θ_t| : 1 <= s,t <= 19, j != s != t != j },
     c₃ = max{ |θ_i-θ_j| : 1 <= i <= 19, i != j },

     c₄ = c₃+c₁/{4c₂},
     c₅ = max{ 1+|log(c₁/2)|/log(4), 1+|log(c₄)|/log(4)},

{i_k : 1 <= k <= 18}={1,..,19}-{j}とする。
18次正方行列M(各要素は実数)を
     M = [log|ε₁^(i₁)|,...,log|ε₁₈^(i₁)|;
             log|ε₁^(i₂)|,...,log|ε₁₈^(i₂)|;
             .............. ;
             log|ε₁^(i₁₈)|,...,log|ε₁₈^(i₁₈)|]
で定義する。
     M^-1 = (m_r,s), 1 <= r <= 18, 1 <= s <= 18,
     c₆ = max{ |m_r,1|+...+|m_r,18| : 1 <= r <= 18 }*c₅
とする。

--------------------------------------------------------------
[定理1]
α₁,...,α_nを0,1と異なる代数的数、
数体Q(α₁,...,α_n)のQ上の次数をd、
b₁,...,b_nを少なくとも１つが0でない有理整数、
B = max{ |b₁|, ..., |b_n|, e^(1/d) },
log(A_i) = max{ h(α_i), (1/d)*|log(α_i)|, 1/d },
h(α)はαの絶対対数Weil height、つまり、
h(α)=(1/[Q(α):Q])*log|a₀Π_i=1^smax{1,|αⁱ|}|,
[ ここで、a₀はαの最小多項式の最上位項の係数, α=α¹,...,α^sはαの共役数である。]
とする。
Λ=b₁log(α_i)+...+b_nlog(α_n)!=0ならば、
|Λ| <= exp{-C(n,d)*(Π_i=1ⁿlog(A_i))*log(B)}
が成立する。
ただし、
C(n,d)=18(n+1)!nⁿ⁺¹(32d)ⁿ⁺²log(2nd)
である。
--------------------------------------------------------------

     η_i = max{ |ε_i^(r)| : 1 <= r <= 19 }/min{ |ε_i^(r)| : 1 <= r <= 19 },
     c₇ = C(19,19*18)*(Π_ilog(η_i))*({log(2^2*18)}/{19*18}+log(c_2a)),
     K₁ = {2²⁰c₂}/{ c₁¹⁹},
     K₂ = {19}/{c₆},
     K₃ = sup{ U : U >= 4, U/log(U) <= {c₆c₇}/{19}+{c₆*|log({c₁¹⁹}/{2²⁰c₂})|}/{20*log(4)} },
     C₀ > K₃¹⁸
とする。

これらの定数をpari/gpで計算すると、以下のようになる。

[pari/gpによる計算]

gp>  read("fibo.gp")
time = 1mn, 26,917 ms.
gp>  rr
time = 0 ms.
%1 = [-18.60688390917616363082765156, -7.159004328558012370473565470, -4.272964795975019525174403558, -2.903927591087192886549614601, -2.068910492869702106714912053, -1.479737209451907342087385503, -1.020057641941906578845396551, -0.6324865271560380599775728474, -0.2837705117358578609752929733, 0.04881470128842490530709253784, 0.3841201437685881638420733925, 0.7416297240864516763424933021, 1.146301612239666051911208975, 1.636567055168312758644710613, 2.281894755293989558933374222, 3.230737220442471222961293522, 4.879887791912755764901252344, 8.794247163949986621842210375, 34.28354283980115363694008583]~
gp>  for(i=1,19,print("c1_",i,"=",cc1(19,rr,i)))
c1_1=11.44787958061815126035408609
c1_2=2.886039532582992845299161911
c1_3=1.369037204887826638624788956
c1_4=0.8350170982174907798347025482
c1_5=0.5891732834177947646275265504
c1_6=0.4596795675100007632419889513
c1_7=0.3875711147858685188678237042
c1_8=0.3487160154201801990022798741
c1_9=0.3325852130242827662823855111
c1_10=0.3325852130242827662823855111
c1_11=0.3353054424801632585349808546
c1_12=0.3575095803178635125004199096
c1_13=0.4046718881532143755687156728
c1_14=0.4902654429286467067335016388
c1_15=0.6453277001256768002886636088
c1_16=0.9488424651484816640279192995
c1_17=1.649150571470284541939958822
c1_18=3.914359372037230856940958030
c1_19=25.48929567585116701509787545
time = 41 ms.
gp>  print("c2=",cc2(19,rr))
c2=103.9352081747939200450736036
time = 176 ms.
gp> for(i=1,19,print("c2a_",i,"=",cc2a(19,rr,i)))
c2a_1=4.620106839569096201299976213
c2a_2=14.35966025429605474241033627
c2a_3=28.16322850695305769350335521
c2a_4=44.53498079293509127750908375
c2a_5=61.70078371814526310216034559
c2a_6=77.80045618076117128404873662
c2a_7=91.08934885730108499433677891
c2a_8=100.1274040278466681460424644
c2a_9=103.9352081747939200450736036
c2a_10=102.9352081747939200450736036
c2a_11=101.1001266346521128932474828
c2a_12=93.82101896651950788432350680
c2a_13=81.88668943323107632355976649
c2a_14=66.59040781992110705670505877
c2a_15=49.58976358565559988125448481
c2a_16=32.72704032539196799940417444
c2a_17=17.82957575649011129888763000
c2a_18=7.000157233612716027377829217
c2a_19=2.075005422730698544332772877
time = 182 ms.
gp>  for(i=1,19,print("c3_",i,"=",cc3(19,rr,i)))
c3_1=52.89042674897731726776773739
c3_2=41.44254716835916600741365130
c3_3=38.55650763577617316211448939
c3_4=37.18747043088834652348970043
c3_5=36.35245333267085574365499788
c3_6=35.76328004925306097902747133
c3_7=35.30360048174306021578548238
c3_8=34.91602936695719169691765868
c3_9=34.56731335153701149791537880
c3_10=34.23472813851272873163299329
c3_11=33.89942269603256547309801244
c3_12=33.54191311571470196059759253
c3_13=33.13724122756148758502887685
c3_14=32.64697578463284087829537522
c3_15=32.00164808450716407800671161
c3_16=31.05280561935868241397879231
c3_17=29.40365504788839787203883348
c3_18=27.40113107312615025266986193
c3_19=52.89042674897731726776773739
time = 17 ms.
gp>  for(i=1,19,print("c5_",i,"=",cc5(19,rr,i)))
c5_1=3.862842809453124807166655831
c5_2=3.686641206935414212856411388
c5_3=3.634512843801405866330318555
c5_4=3.608411314623614796598461768
c5_5=3.592018533508897142483479567
c5_6=3.580225878975147599865096583
c5_7=3.570890758433111497948666998
c5_8=3.562926128927795774715458118
c5_9=3.555684980448326043214576902
c5_10=3.548711181321518112038973113
c5_11=3.541611561634266122541169874
c5_12=3.533965029631231992191444870
c5_13=3.525211985523618349272343658
c5_14=3.514464780895352870187194686
c5_15=3.500072138359590909564680998
c5_16=3.478378873371045369066047772
c5_17=3.439059106977884768396965675
c5_18=3.388329592452024534791878568
c5_19=3.863303056592948377872332737
time = 2,987 ms.
gp>  for(i=1,19,print("c6_",i,"=",cc6(19,rr,i)))
c6_1=5.676589106117976859144965456
c6_2=5.160991509139588249177926742
c6_3=6.558568862820006554994108976
c6_4=5.134210779861354661901160929
c6_5=5.466266853392388269008411503
c6_6=5.322254585078200475207417108
c6_7=6.446722592224162723130788252
c6_8=5.678269911809053295002412637
c6_9=6.582649742003953896077653027
c6_10=7.277728832481616141298202274
c6_11=7.900159880566878336906502549
c6_12=7.071599488373154115737506267
c6_13=6.086319460120409512294725758
c6_14=7.809990406139779089721818795
c6_15=4.852769796165252565993369318
c6_16=7.759118703990632926962591538
c6_17=5.292369154636251193739243275
c6_18=6.261959540207325099910734044
c6_19=5.605071859487379712889845184
time = 4,399 ms.
gp>  for(i=1,19,print("c7_",i,"=",cc7(19,rr,i)))
c7_1=2.534565069217360265614535453 E149
c7_2=4.327158471426955300098949950 E149
c7_3=5.391951452156927997757681950 E149
c7_4=6.116348470936867936004555142 E149
c7_5=6.631711499939518613498902342 E149
c7_6=6.998212476122484522744983958 E149
c7_7=7.247488681166411527813050059 E149
c7_8=7.397032879812428361110371433 E149
c7_9=7.456033743114033812397949640 E149
c7_10=7.440750983367826759957334523 E149
c7_11=7.412315639558635413550986550 E149
c7_12=7.294197122600733174970624762 E149
c7_13=7.079130413809168723743840534 E149
c7_14=6.752266672598360468622664467 E149
c7_15=6.286295472554628429883522776 E149
c7_16=5.629357546212027166235796775 E149
c7_17=4.669292097652781670454845248 E149
c7_18=3.191395511288956410070181666 E149
c7_19=1.269236804334598581753498915 E149
time = 898 ms.
gp>  for(i=1,19,print("K1_",i,"=",KK1(19,rr,i)))
K1_1=8.348080085014324979862971935 E-13
K1_2=0.1957128607575020150002868580
K1_3=278915.6228421545621823813364
K1_4=3350816180.631183451532242681
K1_5=2527811851420.498781201793457
K1_6=282301901049113.5769617049664
K1_7=7222473598813868.037646673165
K1_8=53752247168554086.68294132434
K1_9=132192499523296790.6077680112
K1_10=132192499523296790.6077680112
K1_11=113237729347405716.9367406166
K1_12=33488569985733297.03488804418
K1_13=3179837480505639.456350674281
K1_14=83017229741756.24832054701184
K1_15=448266997678.8468386200628719
K1_16=295579597.4381343647604927268
K1_17=8117.395775049208161778782351
K1_18=0.0005981490204413771706303033285
K1_19=2.072830239889549132693814618 E-19
time = 2,981 ms.
gp>  for(i=1,19,print("K2_",i,"=",KK2(19,rr,i)))
K2_1=3.347080376052344481585522484
K2_2=3.681463138692040620068554186
K2_3=2.896973470494371819946377526
K2_4=3.700666142209510165158736238
K2_5=3.475863968881892373639982472
K2_6=3.569915661920714170193607744
K2_7=2.947233998081011270119581431
K2_8=3.346089617981323742889411562
K2_9=2.886375660968380226874824347
K2_10=2.610704580692824930712832102
K2_11=2.405014618341704916599564736
K2_12=2.686803746626071383607115490
K2_13=3.121755294721928869546892741
K2_14=2.432781477562796895908782363
K2_15=3.915289782551430205288426414
K2_16=2.448731708438486785233484592
K2_17=3.590074585661794286706660862
K2_18=3.034193989597533462817318465
K2_19=3.389787049355986956157088513
time = 4,367 ms.
gp> for(i=1,19,print("K3_",i,"=",KK3(19,rr,i)))
K3_1=2.640225010001694665256866643 E151
K3_2=4.103315024204763567189367883 E151
K3_3=6.506194496294300345993895902 E151
K3_4=5.775503752915739715674430905 E151
K3_5=6.669899842976357574077009212 E151
K3_6=6.853609883662382305627216697 E151
K3_7=8.602911054631473632457423259 E151
K3_8=7.731430851542582959797977479 E151
K3_9=9.038342749315870839514972427 E151
K3_10=9.975053104593329240266875117 E151
K3_11=1.078921155438269566045573946 E152
K3_12=9.500297673236361598254282540 E151
K3_13=7.931451408496341670187975697 E151
K3_14=9.713364206619144862488068840 E151
K3_15=5.610122267857494603252824134 E151
K3_16=8.040929640419795432476172282 E151
K3_17=4.541782884300881568335725914 E151
K3_18=3.670719388462933076033202982 E151
K3_19=1.302846342307270423194172694 E151
time = 8,252 ms.
gp>  for(i=1,19,print("c0_",i,"=",cc0(19,rr,i)))
c0_1=3.886305454175473521459296800 E2725
c0_2=1.087495545796007032411964427 E2729
c0_3=4.364020228921332832333903770 E2732
c0_4=5.112315725970643925980001537 E2731
c0_5=6.825706730252138072331780034 E2732
c0_6=1.113137576216018576163351265 E2733
c0_7=6.662201895377302486976760357 E2734
c0_8=9.742664959245291649513751711 E2733
c0_9=1.620311509275040006927887480 E2735
c0_10=9.560352288543547700647294794 E2735
c0_11=3.924774946097463537229090136 E2736
c0_12=3.974384119572541886040195151 E2735
c0_13=1.542936390915919004311711515 E2734
c0_14=5.924532901851158034822967495 E2735
c0_15=3.030413387432991203961803527 E2731
c0_16=1.974752696865733713535857867 E2734
c0_17=6.761991929001655670069161616 E2729
c0_18=1.463933479895594777914843997 E2728
c0_19=1.169708281683489854336726531 E2720
time = 8,240 ms.
gp>  quit

よって、jの値によらず、Uの最初の上限として、K₃=10¹⁵² を取ることができる。
定数C₀をK₃¹⁸より大きいものとする。例えば、C₀=10²⁹⁰⁰とする。

■LLL-algorithmにより、K₃の上限を下げる。
pari/gpでrealprecision=3000として、j=1,...,19の場合に対して、LLL-algoithmをそれぞれ適用すると、K₃の新しい上限
3351, 2286, 2211, 2203, 2030, 1908, 2354, 2018, 1856, 2704, 2610, 3097, 1903, 1772, 2243, 2909, 2526, 2397, 3068
を得る。
[pari/gp-2.2.7による計算]

gp> read("./fibo.gp")
time = 90 ms.
gp> nf=bnfinit(f(19,x));
time = 27,119 ms.
gp> read("./fibo.gp")
time = 80 ms.
gp> \p 3000
   realprecision = 3005 significant digits (3000 digits displayed)
gp> read("./fibo.gp")
time = 5,668 ms.
<0;for(i=1,19,print("nK3_",i,"=",floor(nKK3(19,rr,C0,K3,i))))
,K3,i))))
nK3_1=3351
nK3_2=2286
nK3_3=2211
nK3_4=2203
nK3_5=2030
nK3_6=1908
nK3_7=2354
nK3_8=2018
nK3_9=1856
nK3_10=2704
nK3_11=2610
nK3_12=3097
nK3_13=1903
nK3_14=1772
nK3_15=2243
nK3_16=2909
nK3_17=2526
nK3_18=2397
nK3_19=3068

■再度LLL-algorithmを適用して、K₃の上限を下げる。
pari/gpでrealprecision=200として、j=1,...,19の場合に対して、さらにLLL-algoithmをそれぞれ適用すると、K₃の新しい上限200を得る。

[pari/gpによる計算]

gp>  \p 200
   realprecision = 202 significant digits (200 digits displayed)
gp> read("./fibo.gp")
time = 271 ms.
gp>  K3=3351;C0=10^150;nKK3(19,rr,C0,K3,1)
time = 54,151 ms.
%8 = 91.592875306291988791714509143763259301280593805871971064555347384857251177016281193269157171043763082247130155375725623402932783409047771219172295181110301887332515368255606781598840377266443310134396
gp>  K3=2286;C0=10^150;nKK3(19,rr,C0,K3,2)
  ***   not a definite matrix in lllgram
gp>  K3=2286;C0=10^160;nKK3(19,rr,C0,K3,2)
time = 1mn, 5,341 ms.
%11 = 96.743469902954319654374607017534079342571941063272850808719470133253919552695396831303515291090062095528756570048718570583508950021296225205476585910181192177380123879172591491741461533324301995518909
gp> K3=3351;C0=10^160;nKK3(19,rr,C0,K3,1))
  ***   not a definite matrix in lllgram
gp>  K3=2211;C0=10^170;nKK3(19,rr,C0,K3,3)
time = 1mn, 16,806 ms.
%19 = 135.79219355634054840353061074018548540217991095147348134654955478487893840624391696890242358568034922773375099497048952854186245965964609756681670983221329871735560500869816329494807849231705838395439
gp>  K3=2203;C0=10^175;nKK3(19,rr,C0,K3,4)
time = 1mn, 22,577 ms.
%24 = 111.95198550715584807935894320089767376034800886363247126338765321834407998872150630645355022117485802910205339195614072009740645787646883105158781324749053864960871463802669882958516179006784834362723
gp>  K3=2080;C0=10^175;nKK3(19,rr,C0,K3,5)
time = 1mn, 18,587 ms.
%25 = 121.11528990740490633142988457429176890656151985406703244342908256346767678492531526478717852469923772408627312726025444241683919277721393383704829535672490935745299667452757210227465600982399566381053
gp>  K3=1908;C0=10^175;nKK3(19,rr,C0,K3,6)
time = 1mn, 20,330 ms.
%33 = 119.26952570594306676256411536951135756045933244137111889628174293841657342178848979675912537488742393624468076423323596796894605234557594317636471889497004056796386663748449973344977956242969837002243
gp>  K3=2345;C0=10^175;nKK3(19,rr,C0,K3,7)
time = 1mn, 23,106 ms.
%34 = 145.49840480681484773909531353119850259161457461342199753142320186158658741888379549265900589818842918229252794553158190038204435196627112743492014373665290611408203522572108486507712206363801357375135
gp>  K3=2203;C0=10^175;nKK3(19,rr,C0,K3,4)
time = 1mn, 22,608 ms.
%35 = 111.95198550715584807935894320089767376034800886363247126338765321834407998872150630645355022117485802910205339195614072009740645787646883105158781324749053864960871463802669882958516179006784834362723
gp>  K3=2018;C0=10^175;nKK3(19,rr,C0,K3,8)
  ***   not a definite matrix in lllgram
gp>  K3=2018;C0=10^176;nKK3(19,rr,C0,K3,8)
time = 1mn, 24,349 ms.
%37 = 129.48779144610066399691165725525814613844178732918262070394457469215646256141988100946418712195205897319951106776514205324415652693688286683118261045239901393286192850794223132292033939218433786354846
gp>  K3=1856;C0=10^175;nKK3(19,rr,C0,K3,9)
time = 1mn, 25,366 ms.
%40 = 149.65442202316226036262484671733079410290485457538077505949001799744575619626018657454721022661022064621220933159067798280341311655949434394993875858495903781895327609500390296042045136179704814229430
gp>  K3=2704;C0=10^180;nKK3(19,rr,C0,K3,10)
time = 1mn, 29,215 ms.
%48 = 169.72243098593712184982015299283477276677760048128700516375222425343067614965770924499607223286122274020506756612332753715919733000835006038819797001500450791989070059436766736441094613207498652588396
gp>  K3=2610;C0=10^170;nKK3(19,rr,C0,K3,11)
time = 1mn, 17,485 ms.
%51 = 174.61455291364894416707903219784223836653200262902135240847950076300742690819550331737275914420772831208168214302438385224521222311185407724970266878253199616816799610159841749825556382990966788316912
gp>  K3=2610;C0=10^165;nKK3(19,rr,C0,K3,11)
time = 1mn, 11,468 ms.
%52 = 169.82749941873878880882733442051707942646228946595092920574812431283914939530824725616172913511797921417549804035750368357695720141033079174891325451273520270230260684603589878168171284009120585629744
gp>  K3=3097;C0=10^150;nKK3(19,rr,C0,K3,12)
time = 55,790 ms.
%53 = 138.64405151344117801946406464178310369339726819752236268451603386210281725909597932263382399013378862373062702071504272115350536605807155017469507944006825676932783901214038518589908653075614803921556
gp>  K3=1903;C0=10^160;nKK3(19,rr,C0,K3,13)
time = 1mn, 5,678 ms.
%58 = 126.10456912793996934940327600243793070321592789191694270445700651488182828198429926549912196133764062963771930598509245953405041280124609090816788263666695771677768685826564107876964332127768005072970
gp>  K3=1772;C0=10^160;nKK3(19,rr,C0,K3,14)
  ***   not a definite matrix in lllgram
gp>  K3=1772;C0=10^165;nKK3(19,rr,C0,K3,14)
time = 1mn, 10,600 ms.
%59 = 165.08111599776145582574894279944384778314522765887728666836537291273461659274849200236917651974906021949869358713252844631305342107212080154573945912515274151624064189428340744017334280645647856766692
gp>  K3=2243;C0=10^155;nKK3(19,rr,C0,K3,15)
time = 59,374 ms.
%60 = 95.299054080296421187133769492742101770496045332048911191533735728263163869437049198906332415650575234060223018585646407961715225378517053393667527191394564510211054223083236765033678100420117816235537
gp>  K3=2526;C0=10^150;nKK3(19,rr,C0,K3,17)
  ***   not a definite matrix in lllgram
gp>  K3=2526;C0=10^155;nKK3(19,rr,C0,K3,17)
  ***   not a definite matrix in lllgram
gp>  K3=2526;C0=10^160;nKK3(19,rr,C0,K3,17)
time = 1mn, 4,518 ms.
%69 = 102.14008557795979211659189432514270118924739716523526549869870417751170815216404453466600765308587799984343906675943320049237298171998143772222121878138303369430221041476083836396181470158370500698381
gp>  K3=2397;C0=10^150;nKK3(19,rr,C0,K3,18)
  ***   not a definite matrix in lllgram
gp>  K3=2397;C0=10^155;nKK3(19,rr,C0,K3,18)
  ***   not a definite matrix in lllgram
gp>  K3=2397;C0=10^160;nKK3(19,rr,C0,K3,18)
  ***   not a definite matrix in lllgram
gp>  K3=2397;C0=10^165;nKK3(19,rr,C0,K3,18)
time = 1mn, 9,318 ms.
%70 = 119.25162866905698881236579967300837826269931985027723377836412262783365534670726802659122994032654923209956777452517226072846107287959764779987688626189000736697880011305739485366715338764775780892540
gp>  K3=3068;C0=10^150;nKK3(19,rr,C0,K3,19)
  ***   not a definite matrix in lllgram
gp>  K3=3068;C0=10^155;nKK3(19,rr,C0,K3,19)
time = 1mn, 2,643 ms.
%71 = 89.374739548994821583542662615258517976262007611075122470391266972916940799453362542883710016887588124679792293361894192684667708249720494803540241368245152665633577990846428519049547160020450885761065
gp> K3=2909;C0=10^200;nKK3(19,rr,C0,K3,16)
time = 4,327 ms.
%72 = 215.19308906932373267781835524996890783347921857100686990625578022876397183224369945744946504558529769739974404302923842508649866498964897589964227226249431835691205869116294927031130362361320187651528

■さらにLLL-algorithmを適用して、K₃の上限を下げる。
pari/gpでrealprecision=200として、j=1,...,19の場合に対して、さらにLLL-algoithmをそれぞれ適用すると、K₃の新しい上限153を得る。

[pari/gpによる計算]

gp>  K3=200;C0=10^150;nKK3(19,rr,C0,K3,1)
time = 54,126 ms.
%83 = 92.435011017368934739563303468667486651786696247948343993267905525930810519984089540735518841869306051955384275764460770891423971016967015961842664403438324853261413591961296791441740481676562435210393
gp>  K3=200;C0=10^150;nKK3(19,rr,C0,K3,2)
  ***   not a definite matrix in lllgram
gp>  K3=200;C0=10^155;nKK3(19,rr,C0,K3,2)
time = 1mn, 1,866 ms.
%84 = 94.277960366190669781151860365751396917171705605044885939734609556141877915891722415914004165184295004618838110249545192739539045751775458330945014022586217277335098051759093205197934480248237936358161
gp>  K3=200;C0=10^150;nKK3(19,rr,C0,K3,3)
  ***   not a definite matrix in lllgram
gp>  K3=200;C0=10^155;nKK3(19,rr,C0,K3,3)
  ***   not a definite matrix in lllgram
gp>  K3=200;C0=10^160;nKK3(19,rr,C0,K3,3)
NG
time = 1mn, 7,570 ms.
%85 = []
gp>  K3=200;C0=10^165;nKK3(19,rr,C0,K3,3)
time = 1mn, 9,836 ms.
%86 = 132.64751906676600727373194526220749050959169603380673173215584328989008949294210433463280246486087314747429440985954246294966357769377379160252773169331553082860953092002148613742351287789956773466338
gp>  K3=200;C0=10^150;nKK3(19,rr,C0,K3,4)
time = 56,699 ms.
%87 = 97.045109734521774878475330770822053450841205831910621086359051572499909636176581149310740760462724896530218901821417778830371850440418109186440327883816120210932861006308759803164383758956300584174867
gp>  K3=200;C0=10^150;nKK3(19,rr,C0,K3,5)
  ***   not a definite matrix in lllgram
gp>  K3=200;C0=10^155;nKK3(19,rr,C0,K3,5)
time = 59,583 ms.
%89 = 108.54002904441905644928852551653125496155803815820792422644311277720749549240085711929846006541392709302454305034790214421170600065814450884973218502866659666183150669819796239516787946192379240840967
gp>  K3=200;C0=10^150;nKK3(19,rr,C0,K3,6)
  ***   not a definite matrix in lllgram
gp>  K3=200;C0=10^155;nKK3(19,rr,C0,K3,6)
time = 59,911 ms.
%90 = 107.00139210029468565576872135281755309850391610223440048873091962757038599424914436098164580369605726095757602957604529111163108937046573710867102656118660277550961785672634026885074242053917682250259
gp>  K3=200;C0=10^150;nKK3(19,rr,C0,K3,7)
time = 57,244 ms.
%91 = 126.80192863843412631975834041299281508738931339277266332037990437298790573642932093998318768219861992035294473625766332334411806771199946914095963693163172844078024650665252525570894654332369836387521
gp>  K3=200;C0=10^150;nKK3(19,rr,C0,K3,8)
  ***   not a definite matrix in lllgram
gp>  K3=200;C0=10^155;nKK3(19,rr,C0,K3,8)
time = 1mn, 3,033 ms.
%92 = 115.72763213449879535823021861321311527797299349549122958317407347764834965331503892173158543667503805322526019962217395541818310837092594714021780875871144180067708373618979555496368794226092688750756
gp>  K3=200;C0=10^155;nKK3(19,rr,C0,K3,9)
time = 1mn, 2,337 ms.
%93 = 134.47142231084389394737741104912061623442799264580258402601499217389808580714413186136907029145280055310204946866454697124650950489588631593625231873743480569096867898227157190818276689118249039391071
gp>  K3=200;C0=10^150;nKK3(19,rr,C0,K3,10)
time = 53,982 ms.
%94 = 144.26059649220666602806940683202856318491003776295515654089805865409284854283931221573839243332102629417643694168378681750505659822756129315340265811405976610263341493223423795966789790066085954438907
gp>  K3=200;C0=10^150;nKK3(19,rr,C0,K3,11)
  ***   not a definite matrix in lllgram
gp>  K3=200;C0=10^155;nKK3(19,rr,C0,K3,11)
  ***   not a definite matrix in lllgram
gp>  K3=200;C0=10^160;nKK3(19,rr,C0,K3,11)
  ***   not a definite matrix in lllgram
gp>  K3=200;C0=10^165;nKK3(19,rr,C0,K3,11)
time = 1mn, 11,473 ms.
%95 = 170.89559685851258148345748822467133276945157580567682913876960289023307442474247702031091380752745657541862003659080002103745577413552094320366404350257269464789364393889707576192286019590756990684732
gp>  K3=200;C0=10^150;nKK3(19,rr,C0,K3,12)
time = 55,791 ms.
%96 = 139.66380336271771449288437069261189750784771134113728292806549345497117389690219839663754337083960785043331801171900796453136282809466124488882559138336630973074577468642254888049315442846700938863108
gp>  K3=200;C0=10^150;nKK3(19,rr,C0,K3,13)
time = 57,272 ms.
%97 = 119.45030686414363445465694027845347140998731845462070173830587055214483295863937098075467242531574210925201112243843346242473303424405531884967797827525574576906090496422965008329602126747239541836891
gp>  K3=200;C0=10^150;nKK3(19,rr,C0,K3,14)
time = 58,431 ms.
%98 = 151.78061100785688305870830532960736880566714796990640961926279262151140346674797738330839476093715698060854064251580630958043481234134319098857343374967523319731694031725782321924112305145436525042648
gp>  K3=200;C0=10^150;nKK3(19,rr,C0,K3,15)
  ***   not a definite matrix in lllgram
gp>  K3=200;C0=10^155;nKK3(19,rr,C0,K3,15)
time = 59,355 ms.
%99 = 95.916441902220803631867736964388719557591329577471010874385366150597114068716558014422694444504224736082696312144690905591178130043161441553597154712327618705025341898452111070456209393812322980224927
gp>  K3=200;C0=10^160;nKK3(19,rr,C0,K3,17)
time = 1mn, 4,528 ms.
%101 = 102.84649828691680123969835318589365695238562348020384778161427719549531014044074859642239913819897785968401049410510424614173102635818638427122925386974754143199723761135254986953804578010740914077246
gp>  K3=200;C0=10^160;nKK3(19,rr,C0,K3,18)
  ***   not a definite matrix in lllgram
gp>  K3=200;C0=10^150;nKK3(19,rr,C0,K3,18)
  ***   not a definite matrix in lllgram
gp>  K3=200;C0=10^155;nKK3(19,rr,C0,K3,18)
  ***   not a definite matrix in lllgram
gp>  K3=200;C0=10^165;nKK3(19,rr,C0,K3,18)
time = 1mn, 9,314 ms.
%102 = 120.07018418042913069247617704204103255714587504565403419003201872440985187878055841579538649835889369808686907602442314420907423447259772303141636434718153189597378864982047397431343654438246646289960
gp>  K3=200;C0=10^150;nKK3(19,rr,C0,K3,19)
  ***   not a definite matrix in lllgram
gp>  K3=200;C0=10^155;nKK3(19,rr,C0,K3,19)
time = 1mn, 2,617 ms.
%103 = 90.180236695616368671338963813599844952250691130548249412643716673214370611575652995461498017870577062637599868546164401625202775886953453957041085260364343963279414765606063132325345840274625088326142
gp>  K3=174;C0=10^140;nKK3(19,rr,C0,K3,11)
time = 2,073 ms.
%104 = 145.05599031029829267870931167844919621423912822643228264144617264630103303932275919290711644298680814723188619442631906419095487630524848249978447059069238115822073694899807467133827577094813095018398
gp> K3=215;C0=10^140;nKK3(19,rr,C0,K3,16)
time = 2,103 ms.
%105 = 153.01869313787233594757409659624940636165772132066291668485764334001887561812050020576775361091883259016571857860305234766040098854061503390683578415644322468345552137196671059187570208669671205565795

■Q(θ)の代数的数 p=Σ_i=0¹⁸a_iθⁱ, q=Σ_i=0¹⁸b_iθⁱに対して、その積をp*q=Σ_i=0¹⁸c_iθⁱ (c_i ∈ Q)とする。
このとき、
     max_{0 <= i <= 18}|a_i| <= K_a,
     max_{0 <= i <= 18}|b_i| <= K_b
ならば、
     max_{0 <= i <= 18}|c_i| <= M*K_a*K_b
となる定数Mを求める。

定数Mをpari/gpで計算すると、
     M = 21083234994753721408385170490818568
であることが分かる。

また、Q(θ)の基本単数の巾乗数
     {ε_k^(i)u_k : 1 <= k <= 18, |u_k| <= 153, 1 < =i <= 19 }
をθの多項式で表現した場合の係数の絶対値の上限をvとすると、
     v = 184179245305773252200186861570622429536060806963472194360061342805404852824034574215719610726708271202590757130057727708787006380431418478360672828663267472837109876003178016558524167858465354674475693056588963004903113042959229151139158498458331201956768187059757952945430044926102974969767151760681423076205981778261218359789665799958068871382830097418880960349141138259727822353295684429447920384626640437911487282068826694236128442669786089474659078954419431505756948019890998720248402951672198125079319384075/131072
であることが分かる。
特に、β_i=A+θ_iBならば、max{|A|,|B|} <= M¹⁷*v¹⁸である。
これより、
     x <= sqrt{5}*M¹⁷*v¹⁸,
     F_m = x¹⁹ <= (sqrt{5}*M¹⁷*v¹⁸)¹⁹
を得る。
また、
     F_m ≒ ((sqrt{5}+1)/2)^m/sqrt{5}
より、F_m = x¹⁹であるならば、
     m <= 883009
であることが分かる。

[pari/gpによる計算]

gp>  m=M(19)
time = 984 ms.
%2 = 21083234994753721408385170490818568
gp>  v=vv(19,nf,153)
time = 18mn, 24,034 ms.
%3 = 184179245305773252200186861570622429536060806963472194360061342805404852824034574215719610726708271202590757130057727708787006380431418478360672828663267472837109876003178016558524167858465354674475693056588963004903113042959229151139158498458331201956768187059757952945430044926102974969767151760681423076205981778261218359789665799958068871382830097418880960349141138259727822353295684429447920384626640437911487282068826694236128442669786089474659078954419431505756948019890998720248402951672198125079319384075/131072
gp>  w=(sqrt(5)+1)/2
time = 0 ms.
%4 = 1.618033988749894848204586834
gp>  s=(((19+1)/2)*log(5)+19*17*log(m)+19*18*log(v))/log(w)
time = 2 ms.
%5 = 883009.8523135340172323720056

■3<=m<=883009である奇数mに対して、F_mが完全19乗数にならないことを確認する。
p_i≡1 (mod 19)なる18個の素数p₁,...,p₁₈を任意に選択する。例えば、
     p₁ = 191,
     p₂ = 229,
     p₃ = 419,
     p₄ = 457,
     p₅ = 571,
     p₆ = 647,
     p₇ = 761,
     p₈ = 1103,
     p₉ = 1217,
     p₁₀ = 1483,
     p₁₁ = 1559,
     p₁₂ = 1597,
     p₁₃ = 1787,
     p₁₄ = 1901,
     p₁₅ = 2053,
     p₁₆ = 2129,
     p₁₇ = 2243,
     p₁₈ = 2281
とする。
各p_i, k(0 <= k < p_i)に関して、k¹⁹ mod p_iを予め計算しておく。
p_iの選び方により、#{ k¹⁹ mod p_i : 0 <= k < p_i }/p_iは十分小さい。
つまり、ランダムに与えた正整数Xが、全てのiに対してmod p_iで19乗-residueになる確率は1.50855・10^-22程度であり、十分に小さいので、この方法による'ふるい'が有効であることに注意する。

各奇数mに対して、あるi(1 <= i <= 18)に対して、F_mがmod p_iで19乗-residueにならないことを確認すれば、F_mは19乗数にならないことが分かる。
もし(不幸にも)、全てのi(1 <= i <= 18)に対して、F_mがmod p_iで19乗-residueになることがあれば、F_mは19乗数になる可能性があるので、別途調べる必要がある。

また、F_m(m=3,5,7,...)の計算には、
     F₁ = 1,
     F₃ = 2,
     F_i+4 = 3F_i+2-F_i (i>=0)
を使う。

pari/gp(gp2c)による計算により、m=3,5,7,...,883009に対して、F_mが完全19乗数にならないことが確認できる。

[gp2c-0.0.2pl6による計算]

bash-2.05a$ gp2c-run -g fibo.gp
Reading GPRC: ./gp2c_gprc ...Done.

                  GP/PARI CALCULATOR Version 2.1.5 (released)
                       i386 running netbsd 32-bit version
                (readline v1.0 enabled, extended help available)

                       Copyright (C) 2002 The PARI Group

PARI/GP is free software, covered by the GNU General Public License, and 
comes WITHOUT ANY WARRANTY WHATSOEVER.

Type ? for help, \q to quit.
Type ?12 for how to get moral (and possibly technical) support.

   realprecision = 28 significant digits
   seriesprecision = 16 significant terms
   format = g0.28

parisize = 100000000, primelimit = 500000
gp>  ll=findp(19)
time = 38 ms.
%1 = [191, 229, 419, 457, 571, 647, 761, 1103, 1217, 1483, 1559, 1597, 1787, 1901, 2053, 2129, 2243, 2281]
gp>  check(19,883009)
#{k:0<=k<191, (k/191)_19}=11
#{k:0<=k<229, (k/229)_19}=13
#{k:0<=k<419, (k/419)_19}=23
#{k:0<=k<457, (k/457)_19}=25
#{k:0<=k<571, (k/571)_19}=31
#{k:0<=k<647, (k/647)_19}=35
#{k:0<=k<761, (k/761)_19}=41
#{k:0<=k<1103, (k/1103)_19}=59
#{k:0<=k<1217, (k/1217)_19}=65
#{k:0<=k<1483, (k/1483)_19}=79
#{k:0<=k<1559, (k/1559)_19}=83
#{k:0<=k<1597, (k/1597)_19}=85
#{k:0<=k<1787, (k/1787)_19}=95
#{k:0<=k<1901, (k/1901)_19}=101
#{k:0<=k<2053, (k/2053)_19}=109
#{k:0<=k<2129, (k/2129)_19}=113
#{k:0<=k<2243, (k/2243)_19}=119
#{k:0<=k<2281, (k/2281)_19}=121
pp=1.500655404171331279116942640 E-23
time = 15,464 ms.

■以上により、F_m=x¹⁹ならば、m<=2である。
m<=2の範囲で、F₀=0, F₁=F₂=1は、(自明な)完全19乗数である。
よって、Fibonacci数列に現れる完全19乗数は、0,1に限ることが証明できた。

■不定方程式
     v²-5u³⁸ = ±4 ----- (1)
の整数解(u,v)は、
     (0,±1), (±1,±1)
の６個に限る。

[証明]
(u,v)を(1)の整数解とする。
必要に応じてu,vの符号を反転することにより、u,v >= 0として良い。
(v,u¹⁹)は、不定方程式
     x²-5y² = ±4 ----- (2)
の整数解である。

２次不定方程式(2)の整数解(x,y)は、
     {(x+sqrt{5}*y)/2}{(x-sqrt{5}*y)/2} = ±1
を満たすので、(x+sqrt{5}*y),(x-sqrt{5}*y)は、整数環Z[(1+sqrt{5})/2]の単数である。
Z[(1+sqrt{5})/2]は、UFDであり、その基本単数は、(1+sqrt{5})/2である。
よって、ある整数mが存在して、
     (x+sqrt{5}*y)/2 = ±{(1+sqrt{5})/2}^m,
     (x-sqrt{5}*y)/2 = ±{(1-sqrt{5})/2}^m
となる。
これらより、
     y = ±{((1+sqrt{5})/2)^m-((1-sqrt{5})/2)^m}/{sqrt{5}}
を得るので、|y|はm番目のFibonacci数F_mに一致する。

u >= 0なので、このとき、u¹⁹ = F_mとなる。
完全19乗数になるF_mは、0,1に限るので、(1)の非負整数解(u,v)は、
     (0,1), (1,1)
の２個に限る。
よって、(1)の整数解(u,v)は、
     (0,±1), (±1,±1)
の６個に限る。

[参考文献]

[1]J. Mc Laughlin, "Small Prime Powers in the Fibonacci Sequence", Dec 13, 2000, p1-22.
[2]Nigel P. Smart, "The Algorithmic Resolution of Diophantine Equations", LMSST 41, Cambridge University Press, 1998, ISBN0-521-64633-2.

Last Update: 2019.05.12

H.Nakao