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

Use modular exponentiation by repeated squaring:Since $17=16+1$, multiply the indicated powers to obtain $27^{17}\equiv 6(\mathrm{mod}7)$. Only the binary expansion of the exponent determines which squared powers are multiplied.

Choose the representative $1\le a\le p-1$. Since $p$ is prime and does not divide $a$, their greatest common divisor is one. The extended Euclidean algorithm gives the Bezout identityfor some integers $x,y$. Reducing modulo $p$ gives $ax\equiv 1(\mathrm{mod}p)$, so the residue class of $x$ is a multiplicative inverse of $a$. The argument uses the nonzero condition to exclude the only residue with greatest common divisor $p$.

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:

Absorb the finitely many exceptional initial terms in the Big O notation assumption into a constant $C>0$, so that $|a_n|\le Cn$ for every $n\ge 1$. This is possible because each initial term is finite and each index is positive. We prove the stronger bound $|{}^k{b}_n|\le Cn$ for every $k,n\ge 1$.

The case $k=1$ is the chosen bound. If it holds at $k-1$, the triangle inequality givesMathematical induction completes the proof. Thus ${}^k{b}_n=O(n)$ for every fixed $k$; in fact the same constant works for all the iterated Cesàro means. This is the linear-growth bound for iterated Cesàro means.