<s>[INST] Sum of powers of a matrix with primitive polynomial modulo $2^{r}$ I need to prove an statement in the matrix form, which leads to the following equality modulo $2^{r}$. Which I couldn't prove but with computer simulation for lots of primitive polynomial, it seems to be true.

Question.Prove
  $$ (I+A+A^2+\ldots+A^{2^r(2^m-1)-1}) \equiv 0 \pmod{2^{r}} $$
  Where $A^{m\times m}$ is a matrix with elements in  $\mathbb{N}$ defined as:
  $$
A=\left(\begin{array}{cccc}
a_1  & \ldots & a_{m-1}& a_m\\
1 & \ldots & 0 & 0\\
\vdots  & \ddots & \vdots &\vdots\\
0 &  \ldots &1 & 0
\end{array}\right)
$$
  $a_i's$ are the coefficients of a primitive polynomial mod 2,
  $$P(x)=x^{m}-a_1x^m-\ldots-a_{m-1}x-a_m$$


Examples:
$$m=1\,,r\rightarrow A=[1]\rightarrow 1+A+\ldots+A^{2^r-1}\equiv 2^r\equiv 0 \pmod{2^r}$$
$$m=2\,,r=1\rightarrow A=\left(\begin{array}{cc}
1 & 1\\
1 & 0
\end{array}\right)\rightarrow I+A+A^2+A^3+A^4+A^5\equiv\\
\left(\begin{array}{cc}
1 & 0\\
0 & 1
\end{array}\right)+\left(\begin{array}{cc}
1 & 1\\
1 & 0
\end{array}\right)+\left(\begin{array}{cc}
2 & 1\\
1 & 1
\end{array}\right)+\left(\begin{array}{cc}
3 & 2\\
2 & 1
\end{array}\right)+\left(\begin{array}{cc}
5 & 3\\
3 & 2
\end{array}\right)+\left(\begin{array}{cc}
8 & 5\\
5 & 3
\end{array}\right)\equiv \left(\begin{array}{cc}
20 & 12\\
12 & 8
\end{array}\right)\equiv \left(\begin{array}{cc}
0 & 0\\
0 & 0
\end{array}\right) \pmod{2}$$
$$m=3\,,r=1\rightarrow A=\left(\begin{array}{cc}
1 & 0 & 1\\
1 & 0 & 0\\
0 & 1 & 0
\end{array}\right)\rightarrow I+A+A^2+\ldots+A^{12}+A^{13}\equiv \left(\begin{array}{cc}
276 & 128 & 188\\
188 & 88 & 128\\
128 & 60 & 88
\end{array}\right)\equiv \left(\begin{array}{cc}
0& 0& 0\\
0& 0& 0\\
0& 0& 0
\end{array}\right)\pmod{2}$$
 [/INST] $A$ is the companion matrix of $P(x)$. As $P(x)$ was assumed to be primitive
$$
B:=A^{2^m-1}\equiv I\pmod 2.
$$
Furthermore, $2^m-1$ is the lowest positive exponent for which this congruence holds. So $B=I+2C$ for some integer matrix $C$. We prove by induction that
$$
B^{2^\ell}\equiv I\pmod{2^{\ell+1}}.
$$
The base case $\ell=0$ was already settled. If we already know that for some natural number $k$ we have
$$
B^{2^k}=I+2^{k+1}D
$$
for some integer matrix $D$, then squaring this equation gives
$$
B^{2^{k+1}}=I+2^{k+2}D+2^{2(k+1)}D^2\equiv I\pmod{2^{k+2}}.
$$
So we know that $B^{2^{r}}=A^{2^r(2^m-1)}\equiv I\pmod{2^{r+1}}$.
Again by primitivity $I-A$ is invertible modulo two. By Hensel lifting it is also invertible modulo $2^{r+1}$. Your identity can thus be multiplied by $I-A$. By geometric sum formula it is thus equivalent to
$$I-A^{2^r(2^m-1)}\equiv0\pmod{2^r}.$$
We have just shown that this congruence actually holds modulo $2^{r+1}$.
</s>