$n$번째 피보나치 수를 $f_n$이라 정의합시다.

$(gcd(f_a, f_b))mod(10^9+7) \, (1 \leq a, b \leq 10^{18})$를 쉽게 구할 수 있는 방법이 있을까요?

일반적인 $f_x$만을 구하는 것이라면, 행렬 멱법을 통한 최적화를 통해 $\mathcal{O}(logN)$의 시간에 구할 수 있습니다. 하지만 이 방식은 중간에 $mod$연산이 들어가므로 $f_a$와 $f_b$를 따로 구해서 $gcd$해주는 방식으로는 답을 구할 수 없습니다. 이 문제를 풀기 위해서는 다음의 중요한 성질을 알고 있어야 합니다.

$gcd(f_a, f_b) = f_{gcd(a,b)}$

처음 이 공식을 보면 직관적으로 와 닿지 않을 수 있습니다. 지금부터 이 식을 증명해 봅시다.

$Lemma \ 1. \ \ For \ (k > 0), gcd(f_{k+1},\ f_k) = 1$

$gcd(f_{k+1}, \ f_k) = gcd(f_{k} + f_{k-1}, \ f_k) = gcd(f_k, \ f_{k-1})$ 입니다.

따라서 $gcd(f_{k+1}, \ f_k) = gcd(f_k, \ f_{k-1}) = gcd(f_{k-1}, \ f_{k-2}) = \dots = gcd(f_2,\ f_1)$이고, $gcd(f_2, \ f_1)$은 정의에 의해서 $gcd(1,\ 1)$이므로 1이 됩니다.

$Lemma \ 2. \ \ if \ gcd(n,m) = 1, then \ gcd(n,mk) = gcd(n,k)$

이는 $m$에는 $n$을 나누는 소인수가 없기 때문에 당연한 사실입니다.

$Lemma \ 3.$

$f_a, f_b$가 있을때, $a = nb+m$이라 합시다.

이때, $\begin{bmatrix} f_{a+1}\\ f_{a}\\ \end{bmatrix} = \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}^{nb+m} \times \begin{bmatrix} 1\\ 0 \end{bmatrix} = \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}^{nb} \times \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}^{m} \times \begin{bmatrix} 1\\ 0 \end{bmatrix} = (\begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}^b)^n \times \begin{bmatrix} f_{m+1}\\ f_{m} \end{bmatrix} = \begin{bmatrix} f_{b+1} & f_{b} \\ f_{b} & f_{b-1} \end{bmatrix}^n \times \begin{bmatrix} f_{m+1}\\ f_{m} \end{bmatrix}$ 이다.

즉, $\begin{bmatrix} f_{b+1} & f_b \\ f_b & f_{b-1} \end{bmatrix} \pmod{f_b} = \begin{bmatrix} f_{b-1} & 0 \\ 0 & f_{b-1} \end{bmatrix} = f_{b-1} \times \begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix}$ 이기 때문에 $f_a \equiv f_{b-1}^n f_{m} (mod f_b)$이다.

이때, $gcd(f_b, f_{b-1}) = 1$이므로, $Lemma2$에 따라,

$gcd(f_a, f_b) = gcd(f_{nb+m}, f_b) = gcd(f_{b-1}^nf_m, f_b) = gcd(f_b, f_m)$

이다.

$Lemma \ 4.$

이제 $gcd(a, b) = gcd(b, m) = ... = gcd(g, 0)$에 따라 두 피보나치수의 최대공약수를 구할 수 있다.