一般而言，兔子在出生两个月后，就有繁殖能力，一对兔子每个月能生出一对小兔子来。如果所有的兔子都不死，那么一年以后可以繁殖多少对兔子？

求证:$\left(fib\left(a\right),fib\left(b\right)\right)=fib\left(\left(a,b\right)\right),a,b∈\mathbb{N}^*$

注:$fib\left(a\right)$是斐波那契数列的第$a$项,$\left(a,b\right)$为$a$和$b$的最大公约数

这个命题很有对称的美感，我初三时曾连续花了三天时间找到一种极为复杂的证明，如果大家有什么好方法也可在下方评论

证明:

本证明中记$\frac{1+\sqrt{5}}{2}=x_1$,$\frac{1-\sqrt{5}}{2}=x_2$,$\frac{\sqrt{5}}{5}=x_0$,记$fib(x)=f_x$

斐波那契数列为齐次递归式，由此可知
$$fx=x_0\left(x_1^x-x_2^x\right)
=x_0\left(x_1-x_2\right)\left(x_1^{x-1}+x_1^{x-1}x_2+x_1^{x-2}x_2^2+...+x_2^{x-1}\right)
=x_1^{x-1}+x_1^{x-2}x_2+x_1^{x-3}x_2^2+...+x_2^{x-1}$$

所以$f_x=x_1^{x-1}+x_1^{x-2}x_2+x_1^{x-3}x_2^2+...+x_2^{x-1}$
设$a=mk$,$b=nk$,$m$,$n$,$k$都为整数
$\left(a,b\right)=k,\left(m,n\right)=1$

$$fk=f{(a,b)}=x_1^{k-1}+x_1^{k-2}x_2+x_1^{k-3}x_2^2+...+x_2^{k-1}$$

$$fa=f{mk}=x_1^{mk-1}+x_1^{mk-2}x_2+x_1^{mk-3}x_2^2+...+x_2^{mk-1}$$

$$=(x_1^{mk-1}+x_1^{mk-2}x_2+x_1^{mk-3}x_2^2+...+x_1^{(m-1)k}x_2^{k-1})+...+(x_1^{k-1}x_2^{(m-1)k}+...+x_2^{mk-1})$$

$$=(f_k)(x_1^{(m-1)k}+x_1^{(m-2)k}x_2^k+...+x_2^{(m-1)k})$$

$$fb=(f_k)(x_1^{(n-1)k}+x_1^{(n-2)k}x_2^k+...+x_2^{(n-1)k})$$

记$x_1^{(m-1)k}+x_1^{(m-2)k}x_2^k+...+x_2^{(m-1)k}=A$
记$x_1^{(n-1)k}+x_1^{(n-2)k}x_2^k+...+x_2^{(n-1)k}=B$

由裴蜀定理可知存在整数对(p,q),使得pm-qn=1

• 当p为奇数q为偶数时
  $$A\left(x_1^{ap-a}+x_1^{ap-2a}x_2^a+...+x2^{ap-1}\right)$$
  $$-B\left(x_1^{ap-b}+x_1^{ap-2b}x_2^b+...+x_1^{ap-\frac{b\left(q-4\right)}{2}}x_2^{\frac{\left(q-6\right)b}{2}}+x_1^{\frac{\left(q-6\right)b}{2}}x2^{ap-\frac{b\left(q-4\right)}{2}}+...+x_1^bx_2^{ap-2b}+x_1^{ap-b}\right)=±1$$
• 当q为奇数p为偶数时,可用上述方法得到(A,B)=1
• 当q为奇数且p为奇数时
  若m为偶数(反之同理)
  则$\left(n+p\right)m-\left(q+m\right)n=1$,$n+p$为偶数,$q+m$为奇数,可做变换得$\left(A,B\right)=1$

综上可知$\left(f_a,f_b\right)=f_k$
所以$\left(fib\left(a\right),fib\left(b\right)\right)=fib\left(\left(a,b\right)\right)$
Quod Erat Demonstrandum