What kind of $n^{th}$ order polynomials are solvable by a square matrix with integer entries? Consider a polynomial (monic for simplicity):
$$x^n+a_1x^{n-1}+\dots+a_{n-1}x+a_n=0$$
Here we assume the roots are complex numbers. $a_k$ are integers.
Now consider the corresponding matrix polynomial:
$$X^n+a_1X^{n-1}+\dots+a_{n-1}X+a_nI_m=0$$
Here $X$ is an $m \times m$ matrix, and $I_m$ - $m \times m$ identity matrix. $a_k$ are still integers.

What kind of polynomials can be solved in matrices with integer entries?

Obviously, any $X$ should satisfy at least its characteristic polynomial equation by Cayley–Hamilton theorem, as well as its minimal polynomial. 
But I don't know if every polynomial with integer coefficients is also a characteristic or minimal polynomial of some matrix with integer entries.
 A: For the polynomial $p(x) = x^n + a_1x^{n-1} + \dots + a_n$ we have that the companion matrix $C(p)$ of $p$ given by
$$
C(p) = \begin{bmatrix}0&0&\cdots &0 & -a_n\\
1&0&\cdots & 0 & -a_{n-1}\\0&1&\cdots &0 & -a_{n-2}\\\vdots&\vdots&\ddots&\vdots&\vdots\\
0&0&\cdots&1&-a_1\end{bmatrix}
$$
is an $n \times n$ integer matrix and the minimal polynomial of $C(p)$ is $p$ and so $X = C(p)$ satisfies $p(X) = 0_n$.
A: The problem is not obvious. In particular, the companion matrix concept is far from solving the entirety of the problem. Let $p(x)\in \mathbb{Z}[x]$ be a polynomial of degree $n$; we seek the matrices $A\in M_m(\mathbb{Z})$ or $M_m(\mathbb{Q})$ st $p(A)=0$.
Case 1. $p$ is irreducible over $\mathbb{Z}$. (It is a.s. the case when thecoefficients of $p$ are randomly chosen).
If $n$ does not divide $m$, then no solutions in $M_m(\mathbb{Q})$ and consequently in $M_m(\mathbb{Z})$.
If $m=np$, then the solutions in $M_n(\mathbb{Q})$ are similar to $D=diag(U_1,\cdots,U_p)\in M_m(\mathbb{Z})$ where $U_i=C_p$, the companion matrix of $p$. In $M_m(\mathbb{Z})$, there is an infinity of particular solutions as these: $PDP^{-1}$ where $P\in GL_m(\mathbb{Z})$ ($\det(P)=\pm 1$). Yet it may exist (a priori) other solutions because 2 matrices that are similar over $\mathbb{Q}$ are not necessarily similar over $\mathbb{Z}$. (cf.case 2).
Case 2. $p$ is reducible over $\mathbb{Z}$ and has distinct roots.
Example. $p(x)=x^3-1=(x-1)q(x)$.
$m=2$. Over $\mathbb{Q}$ or $\mathbb{Z}$, the solutions are $I_2$ or the matrices that are similar to $C_q$.
$m=3$. In $M_3(\mathbb{Q})$, the solutions are $I_3$ or are similar to $diag(1,C_q)$ ( similar also to $C_p$).
In $M_3(\mathbb{Z})$, the solutions are $I_3$ or are similar to $D_1=diag(1,C_q)$ or to the permutation $\Delta=\begin{pmatrix}0&0&1\\1&0&0\\0&1&0\end{pmatrix}$. Beware, the last 2 matrices are not similar over $\mathbb{Z}$ because $I_3+\Delta+\Delta^2\not=0\; mod \;3$ and $I_3+D_1+D_1^2=0\; mod\;3$.
$m>3$. Over $\mathbb{Z}$, the solutions are similar to $diag(I_r,C_q,\cdots,C_q,\Delta,\cdots,\Delta)$.
Remark. Such an equation has 0 or an infinity of solutions over $\mathbb{Z}$ except when $p(x)=(x-u)s_1(x)\cdots s_t(x)$ where $u\in \mathbb{Z}$ and, for every $k\leq t$, $s_k$ is an irreducible polynomial of degree $>m$.
