又是好久没写过和OI有过的东西了。然而这篇还是很水，相信大家都早就会了，不用看下去。
我之前写过一个WASM演示，内容是输出斐波那契数$\bmod 998244353$的值。今天我无聊地输入了$998244352$，结果居然是$1$！非常震惊。
难道斐波那契数也满足$F_{p-1}\equiv 1 \pmod{p}$吗？我在脑海里随便思考了一下就推翻了这个猜想。显然如果$5$有$\bmod p$的二次剩余，可以把通项公式写出来，无论二次剩余是什么，因为费马小定理，$a^{p-1}-b^{p-1}$肯定是同余$0$的，而不是1。（例外是$2$，因为$2$的逆元不存在，这个推理不成立）
那么对于二次剩余不存在的质数，比如$998244353$，是否一定成立呢？我试着证了一下。下面令$p=n+1$。
\[\begin{aligned} F_n&=\frac{1}{\sqrt{5}}\left((\frac{1+\sqrt{5}}{2})^n-(\frac{1-\sqrt{5}}{2})^n\right) \\ &=\frac{1}{\sqrt{5}}\left(\sum_{i=0}^{n}(\frac{1}{2})^{n-i}(\frac{\sqrt{5}}{2})^{i}\binom{n}{i}-(\frac{1}{2})^{n-i}(-1)^i(\frac{\sqrt{5}}{2})^{i}\binom{n}{i}\right) \\ &=\sum_{i=1,i\equiv 1\pmod 2}^{n}(\frac{1}{2})^{n-1}(\sqrt{5})^{i-1}\binom{n}{i} \\ &=\sum_{i=0}^{n/2-1}(\frac{1}{2})^{n-1}5^{i}\binom{n}{2i+1} \\ &\equiv 2\sum_{i=0}^{n/2-1}5^{i}\frac{(-1)^\underline{2i+1}}{(2i+1)!} \\ &=-2\frac{5^{n/2}-1}{5-1}\\ &\equiv -\frac{-1-1}{2}\\ &=1\pmod{n+1} \end{aligned}\]第一个等号是平凡的二项式展开。
第二个等号是考虑到$-1$的偶数次幂会使得$\frac{1+\sqrt{5}}{2}$和\(\frac{1-\sqrt{5}}{2}\)相抵消，所以只需要考虑奇数次幂。这里$\frac{1}{2}$的指数减了1是因为两个相等的项加起来，$\sqrt{5}$的指数也减了1是因为和前面的$\frac{1}{\sqrt{5}}$抵消了。
第三个等号中新的$i$等于旧的$\frac{i-1}{2}$。
第四个等号是头一个和取模有关的。首先$(\frac{1}{2})^{n-1}$显然同余$2$。后面把组合数写成了下降幂的形式，之所以有这个中间过程，是因为这里有陷阱，$\frac{a}{b}\equiv \frac{a\bmod p}{b} \pmod{p}$在$p$是质数时才能成立。
第五个等号叫做等比数列求和。不要忘记后面$-1$的奇数次下降幂是负的。
第六个等号是关键。$a^{\frac{p-1}{2}}\equiv -1\pmod{p}$仅在$a$是模$p$的非二次剩余情况下成立。我才疏学浅，自己想了半天这个东西的证明，证了出来。本来想要写在这里当做一个引理嘚瑟一下，后来上wiki搜了一下，发现这个叫做欧拉准则。原来是个老套路啊，这里就不写了。我的证明思路是和wiki上一模一样的。
