Paper 4, Section II, E

Numbers and Sets | Part IA, 2019

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

(b) The Fibonacci numbers F0,F1,F2,F_{0}, F_{1}, F_{2}, \ldots are defined by F0=0,F1=1F_{0}=0, F_{1}=1, and Fn=Fn1+Fn2F_{n}=F_{n-1}+F_{n-2} for all n2n \geqslant 2. Prove by induction that for all n1n \geqslant 1 we have

F2n=Fn(Fn1+Fn+1) and F2n+1=Fn2+Fn+12F_{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 m1m \geqslant 1 and let pp be an odd prime dividing FmF_{m}. Which of the following statements are true, and which can be false? Justify your answers.

(i) If mm is odd then p1(mod4)p \equiv 1(\bmod 4).

(ii) If mm is even then p3(mod4)p \equiv 3(\bmod 4).

Typos? Please submit corrections to this page on GitHub.