<s>[INST] Number of solvable lights out puzzles on m x n rectangle I'm trying to replicate the results on Dr. Brouwer website,
I consulted two of the papers referenced [1] and [2] both of them make use of the same recursively defined polynomial and GCD.

Let $p_n(x)$ be the mod 2 characteristic polynomial of the path of length n. The table has a zero in position (m,n) if and only if $gcd(p_m(x), p_n(x+1)) = 1$ [1]. More generally, $codim(m,n) = degr(gcd(p_m(x), p_n(x+1)))$ [2]
The $p_n(x)$ can be simply computed via $p_0(x) = 1, p_1(x) = x, p_{n+1}(x) = x p_n(x) + p_{n-1}(x)$.

Using a different definition, $Dimensions(Nullspace(Adjacency + I))$, I can verify the $codim(m,n)$ table
But when I try to use $degree(gcd(p_m(x), p_n(x+1)))$ I get weird results.
Here's a discreet example
$codim(5,2) = codim(2,5) = 1$
$codim(5,2) = degree(GCD(p_5(x), p_2(x+1))) = $
$degree(GCD(x(1+x^4), x^2) = degree(x) = 1$ (correct for this m,n and in general about half of m,n pairs)
but this doesn't match $codim(2,5)$
$codim(2,5) = degree(GCD(p_2(x), p_5(x+1))) = $
$degree(GCD(1+x^2, x*(x^3+x^4))) = degree(1) = 0$

Here's my math (double checked by Mathematica) on constructing the various mod 2 characteristic polynomials.
$p_1(x) = x$
$p_2(x) = x*p_1(x) + p_0(x) = x^2 + 1$
$p_3(x) = x*p_2(x) + p_1(x) = x^3 + x + x = x^3$
$p_4(x) = x*p_3(x) + p_2(x) = x^4 + x^2 + 1$
$p_5(x) = x*p_4(x) + p_3(x) = x^5 + x^3 + x + x^3 = x^5 + x$
$p_0(x+1) = 1$
$p_1(x+1) = x+1$
$p_2(x+1) = x*(x+1) + 1 = x^2$
$p_3(x+1) = (x+1)*x^2 + x+1 = x^3 + x^2 + x + 1$
$p_4(x+1) = (x+1)*(x^3+x^2+x+1) + x^2 = x^4 + x^2 + 1$
$p_5(x+1) = (x+1)*(x^4+x^2+1) + x^3+x^2+x+1 = x^5 + x^4$

[1] R. Barua & S. Ramakrishnan, σ-game, σ+-game, and two-dimensional cellular automata. Theor. Comput. Sci. 154 (1996) 349-366.
[2] Klaus Sutner, σ-Automata and Chebyshev-Polynomials, Theor. Comput. Sci. 230 (2000) 49-73. preprint.
 [/INST] $$1+x^2 \equiv (1+x)^2 \mod 2$$
$$x(x^3+x^4) = x^4(1+x)$$
So $\gcd(1+x^2,x(x^3+x^4)) = 1+x$ and is also of degree $1$.
Note that if $\gcd(p(x),q(x+1))=r(x)$, then substituting $x=X+1$ gives $\gcd(p(X+1),q(X+2))=r(X+1)$ showing that when working modulo $2$ the degrees of $\gcd(p(x),q(x+1))$ and $\gcd(p(x+1),q(x))$ are equal.
P.S. Some of the links on Brouwer's site are very out of date. The link to my website should be updated to https://www.jaapsch.net/puzzles/lomath.htm
</s>