Find $k , n $ such that there is $A,B \in M_n(\mathbb{Z})$ with $A^3=O_n$ and $A^kB + BA=I_n$ 
Find all natural numbers $k \ge 1, n \ge 2$ such that there is $A,B
 \in M_n(\mathbb{Z})$ with $A^3=O_n \tag1$ and $A^kB + BA=I_n \tag2$


Obviously $A, B \ne O_n$ and $k \lt 3$ otherwise from (2) $AB=I_n$ therefore A invertible which contradicts (1)
1)Suppose $n=2$
From Cayley Hamilton theorem for $A$ matrix:
$A^2 + t A =O_2 \tag3$ 
But $t$ cannot be not null - otherwise multiplying (3) by $A$ we get $ t A^2 =O_2$ therefore $A^2 = O_2$ and, from (3) $A =O_2$ contradiction. 
It follows that $t=0$ and $A^2=O_2$ and $k \lt 2$ therefore $k=1$. Also from (2), $AB +BA=I_2 \tag4$
That's all I've got. I have no idea how the use the fact that the $A,B$ matrices have integer elements, which I think is essential here.
UPDATE
$n=2$ is valid because of $A=\begin{matrix} 0 & 1 \\ 0 & 0 \end{matrix} , B=\begin{matrix} 0 & 0 \\ 1 & 0 \end{matrix} $
 A: There can be no solution with $k=2$. Assume the contrary. Since $A^3=0$ there is a non-trivial kernel. Not every vector can be in the kernel (since otherwise $A=0$ which is not a solution). So there must be vectors $e_2,e_1$ so that $A$ maps
$$ e_2 \mapsto e_1 \mapsto 0$$
Since $A^2B+BA=I$ we have  $e_1=A^2Be_1$, $e_2=A^2Be_2+Be_1$ from which $0=A^2 e_2=A^4 B e_2+ A^2 Be_1=e_1$. Impossible. 
Suppose there is a solution with $A^2\neq 0$, $k=1$. This time there must be vectors $e_3,e_2,e_1$ so that $A$ maps $$e_3\mapsto e_2 \mapsto e_1 \mapsto 0$$
Since $AB+BA=I$ we have  $e_1=ABe_1$, $e_2=ABe_2+Be_1$ and $e_3=ABe_3+Be_2$.
We then get $e_1=Ae_2=A^2 Be_2+ABe_1=A^2 B e_2+e_1$ and conclude that
$$ e_1 = AB e_1, \ \ \ 0 = A^2 B e_2 $$
But then $e_1=A^2 e_3= A^3 Be_3 + A^2 Be_2=0 + 0$ contradiction.
Only possibility is $k=1$ and $A^2=0$. If $Ae_1=0$, then $e_1=ABe_1$ shows that $e_1$ must be in the image of $A$, whence that there is $e_2$ so that we have
$$ A : e_2\mapsto e_1 \mapsto 0$$
And by the first part $e_2$ is not in the image of $A$. If $Z=\mbox{ker} A$ then also $Z=\mbox{im A}$ and $n=2\mbox{dim} Z$ must be even.
This also yields a solution (simply by setting $B: e_1\mapsto e_2 \mapsto 0$ for each couple of $e_1,e_2$) so there are solutions precisely when $n$ is even and $k=1$
