# 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$

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.$$