If $q(X)$ polynomial over $\Bbb Z/p\Bbb Z$, then $q(X)^p=q(X^p)$

Question

Theorem: Let $p$ be a prime. If $a_i \in \Bbb Z/p\Bbb Z$ for $i=0,1,2...,n$, then the polynomial $$\left(\sum_{i=0}^{n} a_iX^i \right)^p=\sum_{i=0}^{n}a_iX^{pi}$$

I am not sure how to approach this proof. My initial thought was to use binomial expansion but It doesn't seem to lead anywhere. I'd like to mention that I want to keep the level of techniques used at a minimum as the course only assumes bare minimum knowledge (for some reason the course focuses on particular topics in field theory namely, polynomial rings over finite fields without proper treatment of rings and fields).

Answer 1

Given the polynomial

$q(X) = \displaystyle \sum_0^n a_k X^k \in \Bbb Z/p\Bbb Z[X], \tag 1$

where $p \in \Bbb P$ is prime, so that

$a_k \in \Bbb Z/p\Bbb Z, \; 0 \le k \le n, \tag 2$

we have

$(q(X))^p = \left ( \displaystyle \sum_0^n a_k X^k \right )^p, \tag 3$

and we find the expansion of the right-hand side via a simple induction on $n$:

first, for $n = 1$ we have

$q(X) = \displaystyle \sum_0^1 a_k X^k = a_0 X^0 + a_1 X = a_0 + a_1 X; \tag 4$

thus,

$(q(X))^p = \left ( \displaystyle \sum_0^1 a_k X^k \right )^p = (a_0 + a_1 X)^p; \tag 5$

we may use the plain-and-ordinary, vanilla-flavored binomial theorem to write

$(a_0 + a_1 X)^p = \displaystyle \sum_0^p \dfrac{p!}{i!(p - i)!} a_0^{p - i}a_1^iX^i; \tag 6$

the binomial is applicable in this situation since it holds over any unital, commutative ring; inspecting the coefficients in (6), we see that, as integers,

$p \mid \dfrac{p!}{i!(p - i)!}, \; 1 \le i \le p - 1, \tag 7$

whenever $p \in \Bbb P$, since neither $i!$ nor $(p - i)!$ contain $p$ as a factor; $p$ can't can't cancel out of the numerator of the binomial coefficient $p!/(i!(p - i)!)$. Thus, (6) reduces to

$(a_0 + a_1 X)^p = a_0^p a_1^0 X^0 + a_0^0 a_1^p X^p = a_0^p + a_1^p X^p; \tag 8$

now since $a_0, a_1 \in \Bbb Z / p\Bbb Z$, we have by Fermat's Little Theorem that

$a_0^p = a_0, \; a_1^p = a_1, \tag 9$

whence (8) becomes

$(a_0 + a_1 X)^p = a_0 + a_1 X^p, \tag{10}$

and the case $n = 1$ is thus established. The next step is to assume that

$(q(X))^p = \left ( \displaystyle \sum_0^m a_k X^k \right )^p = \displaystyle \sum_0^m a_k X^{kp} = q(X^p) \tag{11}$

binds for polynomials $q(X)$ of degree $m$; now with

$q(X) = \displaystyle \sum_0^{m + 1} a_k X^k \tag{12}$

we may write

$(q(X))^p = \left ( \displaystyle \sum_0^{m + 1} a_k X^k \right )^p = \left (\left ( \displaystyle \sum_0^m a_k X^k \right ) + a_{m + 1}X^{m + 1} \right )^p$ $= \displaystyle \sum_0^p \dfrac{p!}{j!(p - j)!}\left ( \displaystyle \sum_0^m a_k X^k \right )^{p - j} (a_{m + 1}X^{m + 1} )^j, \tag{13}$

again by the binomial theorem, and again by virtue of (7) this is transformed into

$(q(X))^p = \left ( \displaystyle \sum_0^m a_k X^k \right )^p + (a_{m + 1}X^{m + 1} )^p = \left ( \displaystyle \sum_0^m a_k X^k \right )^p + a_{m + 1}^p X^{p(m + 1)}; \tag{14}$

we now substitue in the inductive assumption (11), and again apply Fermat's Little to replace $a_{m + 1}^p$ with $a_{m + 1}$:

$(q(X))^p = \displaystyle \sum_0^m a_k X^{kp} + (a_{m + 1}X^{m + 1} )^p$ $= \displaystyle \sum_0^m a_k X^{kp} + a_{m + 1} X^{(m + 1)p} = \sum_0^{m + 1} a_k X^{kp} = q(X^p); \tag{15}$

thus our induction is complete and we have established

$(q(X))^p = q(X^p) \tag{16}$

for all polynomials $q(Z) \in \Bbb Z / p\Bbb Z[X]$. $OE\Delta$

Answer 2

Hint$_1$: $\binom{p}{k} = \frac{p(p-1)!}{k!(p-k)!}$, where $k, p-k < p$ when $0 < k < p$. Does the factor $p$ change?

Hint$_2$: $(a+b)^p \equiv a^p + b^p$ is a consequence from above. What happens if you plug more numbers, i.e., $a, b, c, \dots$? Induction is a good try.

Hint$_3$: Fermat's little theorem states that $a^p \equiv a$.