Paper 4, Section II, E

Numbers and Sets | Part IA, 2009

Let pp be a prime number and let Zp\mathbb{Z}_{p} denote the set of integers modulo pp. Let kk be an integer with 0kp0 \leqslant k \leqslant p and let AA be a subset of Zp\mathbb{Z}_{p} of size kk.

Let tt be a non-zero element of Zp\mathbb{Z}_{p}. Show that if a+tAa+t \in A whenever aAa \in A then k=0k=0 or k=pk=p. Deduce that if 1kp11 \leqslant k \leqslant p-1, then the sets A,A+1,,A+p1A, A+1, \ldots, A+p-1 are all distinct, where A+tA+t denotes the set {a+t:aA}\{a+t: a \in A\}. Deduce from this that (pk)\left(\begin{array}{l}p \\ k\end{array}\right) is a multiple of pp whenever 1kp11 \leqslant k \leqslant p-1.

Now prove that (a+1)p=ap+1(a+1)^{p}=a^{p}+1 for any aZpa \in \mathbb{Z}_{p}, and use this to prove Fermat's little theorem. Prove further that if Q(x)=anxn+an1xn1++a1x+a0Q(x)=a_{n} x^{n}+a_{n-1} x^{n-1}+\ldots+a_{1} x+a_{0} is a polynomial in xx with coefficients in Zp\mathbb{Z}_{p}, then the polynomial (Q(x))p(Q(x))^{p} is equal to anxpn+an1xp(n1)++a1xp+a0.a_{n} x^{p n}+a_{n-1} x^{p(n-1)}+\ldots+a_{1} x^{p}+a_{0} .

Typos? Please submit corrections to this page on GitHub.