The convergent of the continued fraction of $ \sqrt{N} $ modulo $4$.

Question

Consider the continued fraction of $\sqrt{N}$ for an integer $N$. Let $d$ be its period and $ P_n/Q_n $ be its $ n $-th convergent.

When $ d $ is odd, Theorem 1 of this article that says that $Q_{d-1}$ is odd. However, I calculated the first few values of $ Q_{d - 1} $ and they are all congruent to $ 1 \pmod{4} $.

Is it true that $Q_{d-1} \equiv 1 \pmod{4}$ for all odd values of $d$?

Answer 1

$Q_{d-1}=K(a_1, \ldots, a_{d-1})$ is a palindromic continuant, and since $d=2n+1$ is odd, it looks like this: $$Q_{d-1}=K(a_1, \ldots, a_n, a_n, \ldots,a_1)$$

From Concrete Mathematics (6.133) you have:

$K(x_1, \ldots, x_{m+n})=K(x_1, \ldots,x_{m})\cdot K(x_{m+1}, \ldots, x_{m+n})+K(x_1, \ldots, x_{m-1})\cdot K(x_{m+2}, \ldots, x_{m+n})$

and with $m=n$ and in your notations:

$K(a_1, \ldots, a_n, a_n, \ldots,a_1)=K(a_1, \ldots,a_n)\cdot K(a_n, \ldots, a_1)+K(a_1, \ldots, a_{n-1})\cdot K(a_{n+2}, \ldots, a_1)$

or (indeterminates can be reversed, see wiki link)

$K(a_1, \ldots, a_n, a_n, \ldots,a_1)=K(a_1, \ldots,a_n)^2+K(a_1, \ldots, a_{n-1})^2$

In other words, $Q_{d-1}$ is the sum of two squares, and since it is odd, one of the square must be odd and the other even (one of the form $4x+1$ and the other of the form $4x$), which implies $Q_{d-1}\equiv 1 \mod(4)$