<s>[INST] Determinant of remainder of a primitive matrix modulo 2 I'm trying to prove the following relation for a matrix $A\in \mathbb{Z}^{m\times m} $, $m\geq 2$. It is assumed that the characteristic polynomial of $A$ is primitive modulo $2$:

If $C$ is defined to be the remainder of $A^{2^m-1}\pmod{4}$ , i.e.
  $$A^{2^m-1}\equiv I+2C \pmod{4}$$
  Then prove
  $$\textrm{det}(C)\equiv \textrm{det}(C+I)\equiv 1 \pmod{2}$$


My try:
$$2C\equiv A^{2^m-1}-I\pmod{4}\Rightarrow C\equiv \frac{1}{2}(A^{2^m-1}-I)\pmod{2}$$
$$ \textrm{det}(C)\equiv \textrm{det}(\frac{1}{2}(A^{2^m-1}-I)) \pmod{2}$$
Then for $C+I$
$$C+I\equiv \frac{1}{2}(A^{2^m-1}-I)+I \equiv \frac{1}{2}(A^{2^m-1}+I)\pmod{2}$$

Therefore to prove the statement we must have:
  $$ \textrm{det}(\frac{1}{2}(A^{2^m-1}-I))\equiv \textrm{det}(\frac{1}{2}(A^{2^m-1}+I)) \equiv 1 \pmod{2} $$

Or $$\frac{1}{2^m}\textrm{det}(A^{2^m-1}-I)\equiv \frac{1}{2^m}\textrm{det}(A^{2^m-1}+I) \equiv 1 \pmod{2}$$
$$\Rightarrow\textrm{det}(A^{2^m-1}-I)\equiv \textrm{det}(A^{2^m-1}+I) \equiv 2^{m} \pmod{2^{m+1}}$$
If we call $P_{A^{2^m-1}}(\lambda)$ the characteristic polynomial of $A^{2^m-1}$ then I know that $\textrm{det}(A^{2^m-1}-\lambda I)\equiv P_{A^{2^m-1}}(\lambda)$, and therefore
$$\textrm{det}(A^{2^m-1}-I)= P_{A^{2^m-1}}(1)\,,\textrm{det}(A^{2^m-1}+I)= P_{A^{2^m-1}}(-1)$$
EDIT: I've found out here that if eigenvalues of $A$ are $y_i$ then eigenvalues of $A^n$ will be $y_i^n$, however $y_i$ might be complex. Therefore:
$$P_{A}(\lambda)=\prod_{i=0}^m(\lambda-y_i)\Rightarrow P_{A^{2^m-1}}(\lambda)=\prod_{i=0}^m(\lambda-y_i^{2^m-1})$$
Then I tried to compute each coefficient of $P_{A^{2^m-1}}$ in terms of coefficients of  $P_{A}$, which leads to some kind of generalization of Newton identities I asked it here, however it seems it is not possible to compute all of them (Question has received no general answer yet).
I couldn't continue it further.

Notes:
I've tested a few matrices (of degrees 2,3,4,5) with computer and the statement was true for them.
Primitive here means that the characteristic polynomial of $A$, $q(t)=\textrm{det}(A-tI)=t^m+a_1t^{m-1}+\ldots+a_m$, be primitive (irreducible) modulo 2. 
$$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)$$

Important Edit:

An additional assumption is required for $P_A(x)$  modulo 4. Which is:
If $P_A(x)\equiv f(x^2)+xg(x^2)\pmod 2$ then the above claim is not true only if:
   $P_A(x)\equiv f(x)^2+xg(x)^2\pmod 4$

 [/INST] The claim is not true for $m=2$: Take 
$$
A=\pmatrix{1& 3\\1& 0}, \quad p_A = x^2-x-3
$$
$$
A^3 =\pmatrix{7 & 12 \\ 4 & 3} \equiv \pmatrix{3&0\\0&3} \equiv I + 2I \pmod 4
$$
hence $2C \equiv 2I \pmod 4$, $C\equiv I \pmod 2$, and $C+I\equiv 0\pmod2$, in contradiction to the claim $det(C+I)\equiv 1\pmod 2$.
Here is another counterexample for $m=3$:
$$
A =\pmatrix{0&0&1\\ 1&0&3\\0&1&2},
\quad
A^7 \equiv I \pmod 4,
$$
hence $C=0$. The characteristic polynomial is $p_A=x^3+x+1$ modulo $2$, which is irreducible.

In the constructions above, I exploited the following. Denote by $p_{A,2}$ and $p_{A,4}$ the characteristic polynomials of $A$ modulo $2$ and $4$. The difference between them, $p_{A,4} - p_{A,2}$ was chosen to have degree $m-1$.
This difference has even coefficients.
Then using the factorization of $A^{2^m-1}-I=(A-I)(A^{2^m-2}+\dots + I)$, using $p_{A,4}(A)=0$ to reduce the degree of the polynomial, one gets an expression for $C$, which depends on $A$ and $(p_{A,4}-p_{A,2})/2$. Chosing the latter to get $\det(C)=0$ was then the last step.

In the case $m=2$, the claim is true if and only if $p_{A,4}$ has at least one coefficient from $\{2,3\}$. Here, $p_{A,2}=x^2+x+1$ anyway.
It holds
$$
A^3-1 = (A-I)(A^2+A+I).
$$
If $p_{A,4} = x^2+x+1$, then $A^3-I\equiv 0 \pmod 4$, and $C=0$.
If not, then $p_{A,4} = x^2+x+1 + 2q$, where $q\in \{1,x,1+x\}$. Then 
$$
A^3-1 \equiv (A-I)(2M) \pmod 4,
$$
where $M\in \{I,A,I+A\}$. Hence 
$$
C\equiv (A-I)M \equiv (A+I)M\pmod 2,
$$
and $\det(C)\equiv 1\pmod 2$, since 
$$
\det(A) \equiv p_{A,2}(0) = 1, \ \det(I+A)\equiv p_{A,2}(1) = 1 \pmod 2.
$$
</s>