Which integer matrices are $k$th powers for all $k$? Problem 11401 of AMM (the American Mathematical Monthly) states:

Let $A$ be a nonsingular square matrix with integer entries. Suppose that for every positive integer $k$, there is a matrix $X$ with integer entries such that $X^k = A$. Show that $A$ must be the identity matrix.

What if we assume $\det A=0$?  For example, any idempotent matrix $A=A^2$ is a $k$ th power for all $k$, but are there any other matrices?
 A: The original question was asked about previously on math.SE and there is a beautiful solution by @MooS which generalizes cleanly to this case. Suppose these are $n \times n$ matrices. Working $\bmod p$ for $p$ a prime, the eigenvalues of any matrix in $M_n(\mathbb{F}_p)$ live in a fixed finite field $\mathbb{F}_q$ (e.g. $q = p^{n!}$). By hypothesis, the eigenvalues of $A \bmod p$ must be $k^{th}$ roots for all $k$. But taking $k = q - 1$ this gives that the eigenvalues of $A \bmod p$ are $0, 1$. Since the minimal polynomial of $A \bmod p$ has degree $\le n$ it follows that
$$A^n (A - 1)^n \equiv 0 \bmod p.$$
From here, plugging in $X$ such that $X^{p^m} = A$ gives
$$X^{p^m n} (X^{p^m} - 1)^{n} \equiv X^{p^m n} (X - 1)^{p^m n} \equiv 0 \bmod p$$
(this is actually the key step of the proof!), so as above the only eigenvalues of $X \bmod p$ are $0, 1$. Also as above, since the minimal polynomial of $X \bmod p$ has degree $\le n$ we have $X^n (X - 1)^n \equiv 0 \bmod p$. This gives
$$X^{p^m \lceil \frac{n}{p^m} \rceil} (X - 1)^{p^m \lceil \frac{n}{p^m} \rceil} \equiv 0 \bmod p$$
which gives
$$A^{\lceil \frac{n}{p^m} \rceil} (A - 1)^{\lceil \frac{n}{p^m} \rceil} \equiv 0 \bmod p.$$
Taking $p^m \ge n$ gives $A(A - 1) \equiv 0 \bmod p$, and since this holds for all primes $p$ we conclude that $A^2 = A$, so $A$ is idempotent.

Edit: Here's an even shorter version of the argument which uses only matrix multiplication. First observe that it suffices to prove the result $\bmod p$ for all primes $p$, since then we can reduce $A \bmod p$ to conclude as above. Since every finite monoid embeds into $M_n(\mathbb{F}_p)$ for some $n$, this is equivalent to proving:

Problem: Show that if an element $a$ in a finite monoid $M$ has a $k^{th}$ root for all $k$, then $a$ is idempotent.

Proof. Recall that every element $m$ in a finite monoid satisfies $m^i = m^j$ for some $0 \le i < j \le |M|$, by pigeonhole applied to the set $\{ 1, m, m^2, \dots m^{|M|} \}$. It follows that $m^{|M|!}$ is idempotent, hence that every element with an $|M|!$th root is idempotent. $\Box$
