Past exam of the mathematics course of the University of Cambridge / 2018 / ia / Paper 4 / 5E (Numbers and Sets)

Bezout identity gives integers $b,c$ with $ab+nc=1$ whenever $\gcd (a,n)=1$, so $ab\equiv 1(\mathrm{mod}n)$. If $b,b^{\prime }$ are inverses, multiplying $a(b-b^{\prime })\equiv 0$ by an inverse gives $b\equiv b^{\prime }(\mathrm{mod}n)$. Multiplying Bezout identities for $a$ and $b$ shows that $\gcd (ab,n)=1$.

Wilson theorem states that $(p-1)!\equiv -1(\mathrm{mod}p)$ for prime $p$. Pair the nonzero residues with their unique multiplicative inverses. The only self-inverse residues are $1,-1$, whose product is $-1$, proving the theorem.

Counting one factor of $p$ for every multiple of $p$, another for every multiple of $p^2$, and so on proves Legendre formulaNow $22!\equiv 20!\cdot 21\cdot 22\equiv 2(20!)\equiv -1(\mathrm{mod}23)$, so $20!\equiv 11(\mathrm{mod}23)$. Also $v_5(1000!)=200+40+8+1=249$, while $v_2(1000!)>249$, so $1000!\equiv 0(\mathrm{mod}10^{249})$.

Finally,For $1\le j<p^m$, $v_p(p^m-j)=v_p(j)$, so the second factor is a $p$-adic unit. If $v_p(k)=\ell$, then