(a) State and prove Fermat's theorem. Use it to compute $3^{803}(\bmod 17)$.

(b) The Fibonacci numbers $F_{0}, F_{1}, F_{2}, \ldots$ are defined by $F_{0}=0, F_{1}=1$, and $F_{n}=F_{n-1}+F_{n-2}$ for all $n \geqslant 2$. Prove by induction that for all $n \geqslant 1$ we have

$$F_{2 n}=F_{n}\left(F_{n-1}+F_{n+1}\right) \quad \text { and } \quad F_{2 n+1}=F_{n}^{2}+F_{n+1}^{2}$$

(c) Let $m \geqslant 1$ and let $p$ be an odd prime dividing $F_{m}$. Which of the following statements are true, and which can be false? Justify your answers.

(i) If $m$ is odd then $p \equiv 1(\bmod 4)$.

(ii) If $m$ is even then $p \equiv 3(\bmod 4)$.