Q:

Prove that $tr(A)^p = tr(A^p)\bmod p$ where $A$ is a square integer matrix and $p$ is a prime number.

I'm looking for an elementary proof (one which does not use Galois theory). For the case $p = 3$, we have that $tr(A^3) = tr(A)^3 - 3e_1e_2 + 3e_3$ where the $e_i$ are coefficients of the characterstic polynomial of $A$, and are thus integers, so the result follows. I cannot see a way to generalize this for arbitrary $p$. Any help would be great! 

A:

If $A,B$ are commuting square matrices over $\mathbb{F}_p=\mathbb{Z}/p\mathbb{Z}$ of the same size, then
$$(A+B)^p=A^p+B^p$$
(the binomial formula is valid here, and $p\mid\binom{p}{k}$ for $0<k<p$). (The same holds for $A,B$ over $\mathbb{F}_p[\lambda]$, for the same reason.) It follows, for a matrix $A$ over $\mathbb{F}_p$, denoting by $\chi_A(\lambda)=\det(\lambda I-A)$ its characteristic polynomial, that $(\lambda I-A)^p=\lambda^p I-A^p$ and therefore $\chi_{A^p}(\lambda^p)=\big(\chi_A(\lambda)\big)^p$. But $\big(f(x)\big)^p=f(x^p)$ for any polynomial $f\in\mathbb{F}_p[x]$ (this is usually proven by induction on the degree of $f$ using the same "binomial argument" as above, and the fact that $a^p=a$ for any $a\in\mathbb{F}_p$).
Thus actually we have $\chi_{A^p}(\lambda^p)=\chi_A(\lambda^p)$, i.e. just $\color{blue}{\chi_{A^p}\equiv\chi_A}$. As a corollary (comparing the coefficients), we get $\operatorname{tr}(A^p)=\operatorname{tr}(A)$, and we're done (again by $a^p=a$ for any $a\in\mathbb{F}_p$).

