The original “Lights Out” game works like this: a light pattern is shown on the board, and your task is to turn all the lights off. A light pattern is called solvable if you can complete the game starting from that pattern. Ziheng and Jan are playing on an \(n\times n\) board, and they notice that some patterns are unsolvable. Can you find a rule to decide when a pattern is not solvable?
Suppose that \(x_1+y_1\sqrt{d}\) gives a solution to Pell’s equation \(x^2-dy^2=1\). Define a sequence \(x_n+y_n\sqrt{d} = (x_1+y_1\sqrt{d})^n\). Show that we have the recurrence relations \(x_{n+2} = 2x_1x_{n+1}-x_n\) and \(y_{n+2} = 2x_1y_{n+1}-y_n\).
Prove that the only solution to \(5^a-3^b=2\) with \(a,b\) being positive integers is \(a=b=1\).
Show that Pell’s equation \(x^2-dy^2=1\) has a nontrivial solution.