Past exam of the short options course of the University of Oxford / 2015 / 1 / c / Solution

First simplify the specified residue by modular exponentiation. Modulo the prime number $113$,Therefore $102^{70}\equiv 28\cdot 64\cdot 8\equiv 98$, so the required equation becomes $x^{37}\equiv 97(\mathrm{mod}113)$. Its right side is nonzero, so any solution is a unit modulo $113$.

By Fermat's little theorem, exponents of such units can be reduced modulo $112$. Sinceraising to the $109$th power is the inverse of raising to the $37$th power. There is therefore exactly one residue class of solutions:Now $97\equiv -16$ and $97^3\equiv -4096\equiv 85$. Since $4\cdot 85\equiv 1$, we obtainAs a direct check, $4^4\equiv 30$, $4^8\equiv 109$, $4^{16}\equiv 16$, and $4^{32}\equiv 30$, whence $4^{37}\equiv 30\cdot 30\cdot 4\equiv 97$.