定义
对于互质的\(a, b\)，即\(gcd(a, b) = 1\)，有以下递推式:
引理1:\(\gcd(a, b) = \gcd(b, a \bmod b)\)
证明略
引理2:若\(\gcd(b, c) = 1\)，则\(\gcd(a \times c, b) = \gcd(a, b)\)
证明略
定理1:\(\gcd(f_n, f_{n + 1}) = 1\)
证明:
当\(n \le 2\)时，结论显然成立
当\(n > 2\)时，\(\gcd(f_n, f_{n + 1}) = \gcd(f_n, a \times f_n + b \times f_{n - 1}) = gcd(f_n, b \times f_{n - 1}) = \gcd(f_n, b)\)
令\(g = \gcd(f_n, b)\)，则有\(g|f_n, g|b\)
因为\(f_n = a \times f_{n - 1} + b \times f_{n - 2}, \gcd(a, b) = 1\)，所以\(g|f_{n_1}\)，则有\(g | \gcd(f_n, f_{n - 1})\)
由此可得\(\gcd(f_n, f_{n - 1}) = 1 \Longrightarrow \gcd(f_n, f_{n + 1}) = 1\)
数学归纳即可
定理2:\(f_n = f_{i + 1} \times f_{n - 1} + b \times f_{n - i - 1} \times f_{n - i - 1} (1 \le i < n)\)
数学归纳即可
定理3:\(\gcd(f_n, f_m) = f_{\gcd(n, m)}\)
证明:
不失一般性假设\(n \ge m\)
当\(n = m\)，结论显然成立
当\(n = m + 1\)，根据定理1，有\(\gcd(f_n, f_m) = 1\)，且\(f_{\gcd(n, m)} = f_1 = 1\)，结论成立
当\(n > m + 1\)，根据定理2，有\(f_n = f_{n - m} \times f_{m + 1} + b \times f_{n - m - 1} \times f_m\)
则\(\gcd(f_n, f_m) = \gcd(f_{n - m} \times f_{m + 1} + b \times f_{n - m - 1} \times f_m, f_m) = \gcd(f_{n - m} \times f_{m + 1}, f_m) = \gcd(f_{n - m}, f_m)\)
即可得\(\gcd(f_n, f_m) = \gcd(f_m, f_{n \bmod m})\)
证毕