Paper 4, Section II, $5 E$

Let $n$ be a positive integer. Show that for any $a$ coprime to $n$, there is a unique $b$ $(\bmod n)$ such that $a b \equiv 1(\bmod n)$. Show also that if $a$ and $b$ are integers coprime to $n$, then $a b$ is also coprime to $n$. [Any version of Bezout's theorem may be used without proof provided it is clearly stated.]

State and prove Wilson's theorem.

Let $n$ be a positive integer and $p$ be a prime. Show that the exponent of $p$ in the prime factorisation of $n$ ! is given by $\sum_{i=1}^{\infty}\left\lfloor\frac{n}{p^{2}}\right\rfloor$ where $\lfloor x\rfloor$ denotes the integer part of $x$.

Evaluate $20! \mod 23$ and $100! \mod 10^{249}$

Let $p$ be a prime and $0<k<p^{m}$. Let $\ell$ be the exponent of $p$ in the prime factorisation of $k$. Find the exponent of $p$ in the prime factorisation of $\left(\begin{array}{c}p^{m} \\ k\end{array}\right)$, in terms of $m$ and $\ell$.

*Typos? Please submit corrections to this page on GitHub.*