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

In modular arithmetic, calculations may be performed after replacing each input by its remainder. For a positive modulus $m$, write $[a{]}_m$ for the remainder in $\{0,\dots ,m-1\}$. ThenEquivalently, if $a\equiv a^{\prime }(\mathrm{mod}m)$ and $b\equiv b^{\prime }(\mathrm{mod}m)$, addition and multiplication give $a+b\equiv a^{\prime }+b^{\prime }$ and $ab\equiv a^{\prime }{b}^{\prime }$, and a fixed nonnegative integer exponent gives $a^k\equiv (a^{\prime }{)}^k$. One cannot in general reduce the exponent modulo $m$ by this rule.