$gcd(f_i,f_{i-1}) = 1$

\begin{eqnarray}
gcd(f_i,f_{i-1}) &=& gcd(f_{i-1}+f_{i-2},f_{i-1})\\
&=& gcd(f_{i-2},f_{i-1})\\
&=& gcd(f_{i-3},f_{i-2})\\
&=& \dots\\
&=& gcd(f_1,f_2)\\
&=& 1\\
\end{eqnarray}

$f_{i+j} = f_{i-1}\cdot f_j + f_i\cdot f_{j+1}$

首先,$j = 1$时有 $f_{i+1} = f_{i-1}+f_i$ 显然成立,

当$j = 2$时有

\begin{eqnarray}
f_{i+2} &=& f_{i+1} + f_{i}\\
&=& (f_{i}+f_{i-1}) + f_{i}\\
&=& f_{i-1} \cdot 1 + f_{i} \cdot 2\\
&=& f_{i-1} \cdot f_j + f_i \cdot f_{j+1}\\
\end{eqnarray}

然后我们证明,当$j = k-1$和$j = k-2$成立时,$j = k$也成立

也就是说已知

$$
\begin{cases}
f_{i+k-1} &=& f_{i-1}\cdot f_{k-1} + f_{i}\cdot f_k\\
f_{i+k-2} &=& f_{i-1}\cdot f_{k-2} + f_{i}\cdot f_{k-1}\\
\end{cases}
$$

然后我们累加上面两式,可以得到

$$
f_{i+k-1}+f_{i+k-2} = f{i-1}\cdot f_{k-1} + f_{i}\cdot f_k + f{i-1}\cdot f_{k-2} + f_{i}\cdot f_{k-1}
$$

$$
\therefore
\begin{eqnarray}
f_{i+k} &=& f_{i-1}\cdot (f_{k-1}+f{k-2}) + f_{i}\cdot (f_{k}+f_{k-1})\\
&=& f_{i-1}\cdot f_{k} + f_{i}\cdot f_{k+1}\\
\end{eqnarray}
$$

$ gcd(f_{i+j},f_{i}) = gcd(f_{i},f_{j}) $

$$
\begin{eqnarray}
gcd(f_{i+j},f_{i}) &=& gcd(f_{i-1}\cdot f_j + f_i\cdot f_{j+1},f_{i})\\
&=& gcd(f_{i-1}\cdot f_{j},f_{i})\\
&=& gcd(f_{j},f_{i}) (\because gcd(f_{i},f_{i-1}) = 1)\\
\end{eqnarray}
$$

所以上面的结论可以继续推广,容易得到

$$
gcd(f_{i},f_{j}) = gcd(f_{i\%j},f_{j})
$$

$gcd(f_{i},f_{j}) = f_{gcd(i,j)} $

由上面的结论,我们容易得到,我们不断调用上面的结论,直到$i==1||j==1$,然后可以得到,如果$k=gcd(i,j)$,那么有$gcd(f_{i},f_{j}) = gcd(f_{k},f_{1}) = f_{k} = f_{gcd(i,j)}$

命题得证