(1.1.1)斐波那契循环节
[gcd(fib_n, fib_m) = fib_{gcd(n, m)}
]
考虑设(n < m)，(fib_n = a)，(fib_{n + 1} = b)，那么对应的有(fib_{n + 2} = a + b)，(fib_{n + 3} = a + 2 imes b)，(fib_{n + 4} = 2 imes a + 3 imes b)，那么可以发现(fib_i = fib_{i - n - 1} imes a + fib_{i - n} imes b (i > n + 1))。
那么将(i = m)代入得(fib_m = fib_{m - n - 1} imes a + fib_{m - n} imes b)。
将上式代入(gcd(fib_n, fib_m))，得
[gcd(fib_n, fib_m) = gcd(fib_n, fib_n imes fib_{m - n - 1} + fib_{n + 1} imes fib_{m - n})
]
根据辗转相除法法，得到(gcd(fib_n, fib_m) = gcd(fib_n, fib_{n + 1} imes fib_{m - n}))。
接下来证明(gcd(fib_i, fib_{i + 1}) = 1)。
运用更相减损术，可以得到
[gcd(fib_i, fib_{i + 1})
]
[= gcd(fib_{i + 1} - fib_{i}, fib_i)
]
[= gcd(fib_{i - 1}, fib_{i})
]
[= gcd(fib_1, fib_2) = 1
]
那么根据这个定理，就可以继续化简上面的式子，得到
[gcd(fib_n, fib_m) = gcd(fib_n, fib_{m - n})
]
如此递归下去当(fib_i = fib_j = gcd(n, m))时，就得到了答案，也就是(fib_{gcd(n, m)})。
[Q.E.D.
]