Past exam of the mathematics course of the University of Cambridge / 2019 / ia / Paper 4 / 5E (Numbers and Sets)

Fermat's little theorem states that for a prime $p$ and integer $a$,if $p\nmid a$, equivalently $a^{p-1}\equiv 1(\mathrm{mod}p)$. For the latter form, multiplication by $a$ permutes the nonzero residue classes modulo $p$. Multiplying the congruences $a,2a,\dots ,(p-1)a$ and cancelling $(p-1)!$ gives $a^{p-1}\equiv 1$. The first form also covers $p\mid a$.

Since $803=50\cdot 16+3$, the theorem gives

We prove both identities by mathematical induction. They hold at $n=1$. Assume they hold at $n$. Using $F_{n-1}=F_{n+1}-F_n$,Adding this to $F_{2n+1}=F_n^2+F_{n+1}^2$ and using $F_{n+2}=F_n+F_{n+1}$ givesThese are precisely the two assertions with $n$ replaced by $n+1$, completing the induction.

True. Write the odd integer as $m=2n+1$. The identity from part (b) and $p\mid F_m$ giveConsecutive Fibonacci numbers are coprime, so $F_{n+1}$ is invertible modulo $p$. HenceThus $-1$ is a quadratic residue modulo the odd prime $p$, which occurs exactly when $\boxed{p\equiv 1(\mathrm{mod}4)}$.

This statement can be false. For example, $m=10$ is even andbut the odd prime divisor $p=5$ satisfies $p\equiv 1(\mathrm{mod}4)$, rather than $3(\mathrm{mod}4)$.