Past exam of the mathematics course of the University of Cambridge / 2003 / ia / Paper 4 / 7C (Numbers and Sets)

For integers $m,n$ not both zero, their greatest common divisor is the greatest positive integer dividing both. For the degenerate pair $(0,0)$ use the conventional value zero. A number $d$ divides both $m,n$ exactly when it divides both $m+kn,n$: one direction uses closure of divisibility under sums; the reverse subtracts $kn$. The positive common-divisor sets are therefore identical, provingThis also holds for $(0,0)$ under the stated convention and does not depend on the signs of the integers.

Bezout identity states that there exist integers $a,b$ such that $am+bn=\gcd (m,n)$. If a prime $p$ divides $mn$ but does not divide $m$, then $\gcd (p,m)=1$, so choose $a,b$ with $ap+bm=1$. Multiplying by $n$ gives $apn+bmn=n$. Both terms on the left are divisible by $p$, so $p\mid n$. Thuswhich proves the Euclid lemma from the requested identity. The separately numbered entries use these arithmetic facts for the Fibonacci numbers.

Write $F_n=x_n$. For $n\ge 1$, the recurrence and the previously proved greatest common divisor invariance giveRepeating reaches $\gcd (F_1,F_0)=\gcd (1,0)=1$. This also gives the $n=0$ case directly. Applying the same invariance once more,Thus both requested greatest common divisors equal one for every $n\ge 0$. This is the adjacent-index instance of Fibonacci gcd reduction, derived directly rather than assuming the stronger general formula.

Put ${\mathbf{v}}_n=(F_{n+1},F_n{)}^T$. The Fibonacci recurrence matrix modulo an integer is $A=\left(\begin{array}{cc}1& 1\\ 1& 0\end{array}\right)$, so ${\mathbf{v}}_{n+r}=A^r{\mathbf{v}}_n$. Direct matrix multiplication givesTaking the second coordinate provesFor explicit arithmetic behind the second power, squaring $A^2=\left(\begin{array}{cc}2& 1\\ 1& 1\end{array}\right)$ gives $A^4=\left(\begin{array}{cc}5& 3\\ 3& 2\end{array}\right)$, whose square is the displayed $A^8$. Thus the modular period assertions follow from calculations and the recurrence, not from quoting a period theorem.

The same recurrence matrix hasTherefore ${\mathbf{v}}_{n+5}\equiv 3{\mathbf{v}}_n(\mathrm{mod}5)$, and in particular $F_{n+5}\equiv 3F_n(\mathrm{mod}5)$. Starting from $F_0=0$ and iterating,Consequently every nonnegative index divisible by five has a Fibonacci number divisible by five, including index zero. This directly proves the requested divisibility without assuming a general Fibonacci divisibility theorem.