斐波那契公约数证明
已知 \(F_n\) 为斐波那契数列， 求证：\(∀ n,m∈Z^+, (F_n,\ F_m) = F_{(n,\ m)}\)
证明：
令 \(n < m\), \(F_n = F_1 * a,\ F_{n + 1} = F_2 * b\)
\(F_{n + 2} = F_1 * a + F_2 * b\)
\(F_{n + 3} = F_2 * a + (F_2 + F_2) * b = F_2 * a + F_3 * b\)
\(F_{n+4} = F_3 * a + F_4 * b\)
\(F_{n + 5} = F_4 * a + F_5 * b\)
.......
\(F_m = F_{n + (m - n)} = F_{m - n - 1} * a + F_{m - n} * b = F_{m - n - 1} * F_n + F_{m - n} * F_{n + 1}\)
\((F_n, F_m) = (F_n, F_{m - n - 1} * F_n + F_{m - n} * F_{n + 1})\)
\(= (F_n, F_{m - n} * F_{n + 1})\)
又 \((F_n, F_{n + 1}) = 1\)
因此有： \((F_n,\ F_m) = (F_n, F_{m - n})\)
\(= (F_n, F_{m \% n})\)
\(= F_{(n,\ m)}\)
标签：.......,证明,斐波,公约数,那契,为斐波 From： https://www.cnblogs.com/llinzy/p/17021750.html