斐波那契数列中项是完全平方数

isee

在斐波那契数列（Fibonacci sequence）：$F_1=F_2=1,F_n=F_{n-1}+F_{n-2},n\geqslant 2$中，第1项，第2项，第12项都是完全平方数，是否还有其他的项也能是完全平方数？

realnumber

编了个小程序，搜索到$F_{90}=7540113804746346429$也不是完全平方。也只有1，2，12三项.再大就溢出了。

var
a,b,c:int64;
i:longint;

begin
a:=1;
b:=1;
for i:=1 to 90 do
  begin
   c:=a+b;
   if c=trunc(sqrt(c))*trunc(sqrt(c)) then write(' ',i+2,' ',c,'  ');
   a:=b;
   b:=c;

  end;
  write(c);
end.

zhcosin

回复 2# realnumber
这才多大就溢出了，啥语言？

realnumber

pascal ,陪儿子一起学

abababa

往上没有了，就这三个解，以前看网友解过，但找了一遍没找到放哪了。他还用了另一个叫卢卡斯数列的，貌似和斐波那契数列相似的那个。

zhcosin

编程显示斐波那契数列中，下标在200以内的平方数，每一个括号中，第一个是下标，第二个是项.

realnumber

回复 6# zhcosin

好奇怪，连续那么多符合要求的完全平方数。
你那数据是不是太大，不精确了，

abababa

回复 7# realnumber

用Mathematica算Sqrt[Fibonacci[132]]就不能得出整数，第132项不是完全平方数。并且已经有人证明过了，只有1，2，12三项是完全平方数，其它的肯定都是不对的了。

zhcosin

回复 8# abababa
恩，它在判断大整数是否相等时存在有效数字即精度的问题，也就是说，判断整数$x$是否平方数的函数(sequare? x)存在不准确的问题，后面的应该都不是。

isee

的确是有且仅有三项，如何论证呢？

isee

给出的参考答案
132．在斐波那契序列 $\left(F_1=F_2=1, F_n=F_{n-1}+F_{n-2}, n \geqslant 3\right)$中，第 1 项，第 2 项和第 12 项都是完全平方数，是否还有其他的项也能是完全平方数？

解 除了题目中所给出的几项之外，在斐波那契序列中不存在其它的完全平方数．我们分成以下几步加以证明：
（1）$F_n$ 之间的关系：设 $\omega=\frac{\sqrt{5}+1}{2}$ ，因而 $\omega^2=\omega+1$ ．如果设 $F_0=0$，那么由数学归纳法就得出对所有的正整数成立 $\omega^n=F_n \omega+F_{n-1}$，利用此式和指数律就得出对任意正整数 $m, n, k$ 成立
\[\tag*①
\begin{gathered}
F_{m+n}=F_m F_n+F_m F_{n-1}+F_{m-1} F_n \\
F_{k n}=k F_n\left(F_{n-1}\right)^{k-1}+\left(F_n\right)^2 P_k\left(F_n, F_{n-1}\right) \\
F_{k n-1}=\left(F_{n-1}\right)^k+\left(F_n\right)^2 Q_k\left(F_n, F_{n-1}\right)
\end{gathered}
\]
其中 $P_k(x, y)$ 和 $Q_k(x, y)$ 都是 $x, y$ 的整系数 $k$ 次齐次多项式．特别
\[\tag*②
F_{2 n}=F_n\left(2 F_{n-1}+F_n\right), F_{2 n-1}=\left(F_{n-1}\right)^2+\left(F_n\right)^2
\]
令 $\bar{\omega}=\frac{1-\sqrt{5}}{2}$，并且将 $\omega^n$ 和 $\bar{\omega}^n=F_n \bar{\omega}+F_{n-1}$ 相乘，我们就得出对任意正整数 $n$ 成立
\[\tag*③
\left(F_{n-1}\right)^2+F_n F_{n-1}-\left(F_n\right)^2=(-1)^n
\]
（2）关于素因子：从③得出 $F_n$ 和 $F_{n-1}$ 是互素的．由此和（1．1）又得出 $F_n$ 的任意素因子 $p$ ，如果不是 $k$ 的因子，就必然同时出现在 $F_n$ 和 $F_{k n}$ 的因子中，并且带有相同的指数。

从①还得出，如果 $p \mid F_n$ ，那么当且仅当 $p \mid F_m$ 时有 $p \mid F_{m+n}$ ．由此又得出对任意整数 $n$ ，当且仅当 $n$ 是一个最小的使得 $p \mid F_m$的整数 $m$ 的倍数时，$p \mid F_n$ ．特别当且仅当 $3 \mid n$ 时， $2 \mid F_n$ ，当且仅当 $4 \mid n$ 时， $3 \mid F_n$ ．
（3）引理 设 $p$ 是一个素数，且让 $m$ 是最小的使得 $p \mid F_m$ 的整数．如果 $m$ 是偶数，那么 $p \not \equiv 13$ 或 $17(\bmod 20)$ ；而如果 $p \equiv 3$ 或 $7(\bmod 20)$ ，那么 $F_{m-1} \equiv-1(\bmod p)$ ．

引理的证明 设 $m=2 m^{\prime}, F_{m^{\prime}} \equiv a(\bmod p), F_{m^{\prime}-1} \equiv$ $b(\bmod p)$ ，那么由②得出 $a+2 b \equiv 0(\bmod p)$ ，并且 $F_{m-1} \equiv a^2+$ $b^2(\bmod p)$ ．那样 $F_{m-1} \equiv 5 b^2(\bmod p)$ ．由（3）又得出 $\left(F_{m-1}\right)^2 \equiv$ $1(\bmod p)$ ，因而 $F_{m-1} \equiv 5 b^2 \equiv \pm 1(\bmod p)$ 。如果 $p \equiv 13$ 或 $17(\bmod 20)$ ，那么 1 和 -1 在模 $p$ 下就都是二次剩余，而 5 不是，这是不可能的．如果 $p \equiv 3$ 或 $7(\bmod 20)$ ，那么 5 和 -1 都不是模 $p$ 下的二次剩余，因此我们必须有 $F_{m-1} \equiv-1(\bmod p)$ 。

我们不加证明的注明如果 $m$ 是 4 的倍数，那么 $p \equiv 11$ 或 $19(\bmod 20)$ 的情况也可以排除．
（4）$F_n$ 对 2 的幂：如果 $n=2^m$ ，利用②我们可以获得以下的 $F_n$和 $F_{n-1}$ 在模 20 下的值：

对 $m \geqslant 6$ ，表中的值以周期 4 重复．（为方便起见，有时我们用 $F(x)$ 代表 $F_x$ ）现在 $F\left(2^m\right)=F\left(2^{m-1}\right) G_m$ ，其中 $F\left(2^{m-1}\right)$ 和 $G_m=$ $2 F\left(2^{m-1}-1\right)+F\left(2^{m-1}\right)$ 互素．如果 $p$ 是 $G_m$ 的素因子，那么 $n=2^m$是最小的使得 $p \mid F_n$ 的整数 $n$ ．那样由（3）就得出 $p \not \equiv 13$ 或 $17(\bmod 20)$ ．另一方面，上表显示 $G_2=3$ 和对所有 $m>2$ 有 $G_m \equiv$ $7(\bmod 20)$ ．那就得出不是所有的 $G_m$ 的素因子都能 $\equiv \pm 1(\bmod$ 5）的．这也就是说当 $m>2$ 时，至少要有一个 $G_m$ 的素因子 $p$ 要使得 $p \equiv 3$ 或 $7(\bmod 20)$ ．那样由（3）就得出 $F\left(2^m-1\right) \equiv-1$ $(\bmod p)$ ，因此 -1 不是模 $p$ 的二次剩余．
i $n$ 是奇数．如果 $n \geqslant 3$ ，那么我们可以把 $n$ 写成 $n=2^m k \pm 1$的形式，其中 $k$ 是奇数而 $m \geqslant 2$ ．由（4）,$F\left(2^m\right)$ 存在一个素因子 $p$使得 $F\left(2^m \pm 1\right) \equiv-1(\bmod p)$ ，并且 -1 不是模 $p$ 的二次剩余．由①我们就得出
\[
F_n=F\left(2^m k \pm 1\right) \equiv(-1)^k \equiv-1(\bmod p)
\]
这就得出 $F_n$ 不可能是一个完全平方数．
ii $n \neq 2^k 3^l$ ．我们称素数 $p$ 是 $F_n$ 的一个好的素因子，如果 $p \geqslant$ 3 并且其指数是奇数．从（2）得出，如果 $p$ 是 $F_n$ 的一个好的素因子，那么 $p$ 就是 $F_{2 n}$ 和 $F_{3 n}$ 的一个好的素因子．如果 $m>1$ 和 6 互素，$n=m 2^k 3^t$ ，那么由 i 可知 $F_m$ 不是完全平方数，由（2）可知，它也不可能是 2 或 3 的倍数，那样 $F_m$ 有一个好的素因子．由此和前面的注就得出 $F_n$ 也有一个好的素因子，因此不可能是完全平方数．

其妙

回复 11# isee
Isee博览群书呀