Chapter 5

Greatest common divisor

1 gcd(a, b)as an integer combination ofaandb

2 Nonnegative integer combinations ofaandb

3 Cassini formula for Fibonacci numbers

4 gcd of generalized Fibonacci and Lucas numbers

Appendix: The Eulerφ-function

Exercise

Project

k rk qk xk yk

− 1 Fn+1 ∗∗∗ 1 0

0 Fn 1 0 1

1 Fn− 1 1 F 1 −F 2

2 Fn− 2 1 −F 2 F 3

3 Fn− 3 1 F 3 −F 4

..

.

n− 3 F 3 1 (−1)n−^2 Fn− 3 (−1)n−^1 Fn− 2

n− 2 F 2 1 (−1)n−^1 Fn− 2 (−1)nFn− 1

n− 1 F 1 1 (−1)nFn− 1 (−1)n+1Fn

n 0 ∗∗∗