打算把之前没有证明的东西补一下
辗转相除法
\[\gcd(a,b)=\gcd(a\bmod b,b)\,\,\,\,\,\,\,\,\,(a \le b) \]
设 \(a=kb+r\,\,\,\,d=\gcd(a,b)\)
可得 \(\frac{a}{d}=k\cdot\frac{b}{d}+\frac{r}{d}\)
由上式可得 \(\frac{r}{d}\) 为整数
所以 \(d\mid r\)，由此得证
斐波那契数列一些性质
\[f_{n+m}=f_{n}\cdot f_{m+1}+f_{n-1}\cdot f_{m} \tag{Lemma 1} \]
对于 \(m=1,2\) 时，易证：
\[f_{n+1}=f_n+f_{n-1}\\ f_{n+2}=2f_n+f_{n-1} \]假设对于 \(m\le k\) 成立，现在证明对于 \(m=k+1\) 成立
\[\begin{aligned} f_{n+k+1} &= f_{n+k}+f_{n+k-1}\\ &= f_n\cdot(f_{k}+f_{k-1})+f_{n-1}\cdot(f_{k-1}+f_{k-2})\\ &= f_{n}\cdot f_{k+2}+f_{n-1}\cdot f_{k+1} \end{aligned} \]可以写成这种形式
\[f_n=f_{(n-m)+m}=f_{n-m}\cdot f_{m+1}+f_{n-m-1}\cdot f_{m} \]\[n \mid m \Rightarrow f_n\mid f_m \]
设 \(m=kn\)
还是数学归纳法，对于 \(k=1\) 时显然成立
假设对于 \(k=p\) 成立，证明对于 \(k=p+1\) 成立
$f_{pn+n}=f_{pn}\cdot f_{n+1}+f_{pn-1}\cdot f_n $
$ f_n\mid f_{pn},f_n \Rightarrow f_n\mid f_{pn}\cdot f_{n+1}+f_{pn-1}\cdot f_n=f_{pn+n} $
由此得证
还有不少，但是先咕
标签：各种,frac,gcd,cdot,mid,证明,填坑,pn From： https://www.cnblogs.com/Rolling-star/p/17076992.html