Paper 4, Section II, E

Numbers and Sets | Part IA, 2013

Let pp be a prime number, and x,nx, n integers with n1n \geqslant 1.

(i) Prove Fermat's Little Theorem: for any integer x,xpx(modp)x, x^{p} \equiv x(\bmod p).

(ii) Show that if yy is an integer such that xy(modpn)x \equiv y\left(\bmod p^{n}\right), then for every integer r0r \geqslant 0,

xprypr(modpn+r)x^{p^{r}} \equiv y^{p^{r}}\left(\bmod p^{n+r}\right)

Deduce that xpnxpn1(modpn).x^{p^{n}} \equiv x^{p^{n-1}}\left(\bmod p^{n}\right) .

(iii) Show that there exists a unique integer y{0,1,,pn1}y \in\left\{0,1, \ldots, p^{n}-1\right\} such that

yx(modp) and ypy(modpn)y \equiv x \quad(\bmod p) \quad \text { and } \quad y^{p} \equiv y \quad\left(\bmod p^{n}\right)

Typos? Please submit corrections to this page on GitHub.