Past exam of the year 1 of the computer science course of the University of Oxford / 2018 / Discrete mathematics, continuous mathematics, and probability / 2 / c / Solution

First prove $a^p\equiv a(\mathrm{mod}p)$ for every nonnegative integer $a$ by mathematical induction. The case $a=0$ is immediate. If it holds at $a$, the binomial theorem and the stated divisibility of the middle binomial coefficients giveThis establishes the induction. For an arbitrary integer $a$, take a nonnegative representative $r$ of its residue class; then $a^p\equiv r^p\equiv r\equiv a(\mathrm{mod}p)$. When $a\not\equiv 0(\mathrm{mod}p)$, part (b) supplies a multiplicative inverse modulo $p$. Multiplying the congruence by that inverse proves Fermat's little theorem: