Let $m, n$ be integers. Explain what is their greatest common divisor $(m, n)$. Show from your definition that, for any integer $k, \quad(m, n)=(m+k n, n)$.

State Bezout's theorem, and use it to show that if $p$ is prime and $p$ divides $m n$, then $p$ divides at least one of $m$ and $n$.

The Fibonacci sequence $0,1,1,2,3,5,8, \ldots$ is defined by $x_{0}=0, x_{1}=1$ and $x_{n+1}=x_{n}+x_{n-1}$ for $n \geqslant 1$. Prove:

(i) $\left(x_{n+1}, x_{n}\right)=1$ and $\left(x_{n+2}, x_{n}\right)=1$ for every $n \geqslant 0$;

(ii) $x_{n+3} \equiv x_{n}(\bmod 2)$ and $x_{n+8} \equiv x_{n}(\bmod 3)$ for every $n \geqslant 0$;

(iii) if $n \equiv 0(\bmod 5)$ then $x_{n} \equiv 0(\bmod 5)$.