GCD of Fibonacci

 

피보나치 수의 경우 눈여겨볼만한 성질들이 몇 가지 존재하는데, 그 중 GCD에 관해서 다음이 성립한다.

$F_n$ 이 $n$-th 피보나치 수 일때,

 

$\forall m, n \in \mathbb{Z}_{> 2}: \gcd \{F_m, F_n\} = F_{\gcd \{m, n\} }$.

 

증명은 유클리드 호제법을 이용하며, 자세한 것은 https://proofwiki.org/wiki/GCD_of_Fibonacci_Numbers