Direct proof that for a prime $p$ if $p\equiv 1 \bmod 4$ then $l(\sqrt{p})$ is odd.

Definition: Assume $p$ is a prime. $l(\sqrt{p})=$ length of period in simple continued fraction expansion of $\sqrt{p}$.

The standard proof of this uses the following:

1. $p$ is a prime implies $p \equiv 1 \bmod 4$ iff $x^2-py^2=-1$ has integer solutions.
2. $p$ is a prime implies $x^2-py^2=-1$ has integer solutions iff $l(\sqrt{p})$ is odd.

I have proofs of (1) and (2) so that I have a proof of the stated question. What I would like is a proof that does not use any equivalences. That is,

Assume $p \equiv 1 \bmod 4$. Show that $l(\sqrt{p})$ is odd.

I will accept contradiction or contrapositive as well. I know this may seem strange but I think there is a lot to learn from this proof.

Also, I asked this on mathoverflow link but got no definative answer. I think a proof may exist using Farey graphs and/or Ford Circles.

We can deduce both of (1) and (2), and the fact that $p$ is a sum of two squares, by playing with quadratic forms. I have the impression this is all "well known to those who know it well". But I've never seen this elementary argument written down in elementary language, so here it is.

We begin with some general discussion of quadratic equations. Let the roots of $a x^2+bx+c$ be $\lambda_1$ and $\lambda_2$. Given a triple of integers $(a,b,c)$, we will think of them as encoding the quadratic equation $a x^2+bx +c$ and we will write the roots of that equation as $\lambda_1$ and $\lambda_2$. We will be performing operations on the coefficients of the equation and seeing how the roots change. For example, the roots of $a (x-1)^2 + b (x-1) + c=a x^2 + (-2a+b) x + (a-b+c)$ will be $\lambda_1+1$ and $\lambda_2+1$. We'll write $E(a,b,c) = (a, -2a+b, a-b+c)$ and $E(\lambda)= \lambda+1$, using the number of inputs of $E$ to make it clear which we are talking about. Here are the operators we will need, as they act on triples $(a,b,c)$ and on the roots $\lambda_i$: $$\begin{array}{|c|l@{}c@{}r|l|} \hline E & (a,&-2a+b,& a-b+c) & 1+\lambda \\ \hline E^{-1} & (a,& 2a+b,& a+b+c) & -1+\lambda \\ \hline F & (a-b+c,& b-2c,& c) & \frac{\lambda}{1+\lambda} \\ \hline F^{-1} & (a+b+c,& b+2c,& c) & \frac{\lambda}{1-\lambda} \\ \hline \end{array}$$

Observe that all of these operators preserve:

• The discriminant $\Delta = b^2 - 4 ac$

• The parity of $b$ (actually, this follows from the previous line, since $\Delta \equiv b^2 \bmod 4$).

• $GCD(a,b,c)$.

We'll be interested in quadratics which can be obtained from $x^2-p$, so we will take $\Delta = 4p$, $b \equiv 0 \bmod 2$ and $GCD(a,b,c) = 1$.

We define $(a,b,c)$ to be reduced if $a>0$ and $c<0$. In a reduced quadratic, we have $b^2 < b^2+4a(-c)=4p$, so there are only finitely many possible values for $b$ and, for each of these values, only finitely many possible values for $a$ and $c$. Write $Q$ for the finite set of reduced triples $(a,b,c)$ with $b^2+4a(-c) = 4p$, $b \equiv 0 \bmod 2$ and $GCD(a,b,c) = 1$.

Let $(a,b,c)$ in $Q$. The roots of $ax^2+bx+c$ are real and of opposite sign; call them $\lambda_- < 0 < \lambda_+$. The following lemmas are left as exercises:

Lemma We have $E (a,b,c) \in Q$ if and only if $\lambda_- < -1$, if and only if $a-b+c<0$. We have $F (a,b,c) \in Q$ if and only if $\lambda_- > -1$, if and only if $a-b+c>0$. Exactly one of these two cases occurs.

Lemma We have $E^{-1} (a,b,c) \in Q$ if and only if $\lambda_+ > 1$, if and only if $a+b+c<0$. We have $F^{-1} (a,b,c) \in Q$ if and only if $\lambda_+ < 1$, if and only if $a+b+c>0$. Exactly one of these two cases occurs.

Draw a directed graph $G$ with vertex set $Q$ and an edge $(a,b,c) \to (a',b',c')$ if $(a',b',c')$ is $E(a,b,c)$ or $F(a,b,c)$. By the above lemmas, every vertex of $G$ has out-degree $1$ and in-degree $1$, so $G$ is a disjoint union of cycles. We will "color" the edges of $G$ with the symbols $E$ and $F$ accordingly. I encourage you to draw this graph for a few small values of $p$ (non-primes, and primes that are $3 \bmod 4$, are good too).

Consider the bijection $\sigma: (a,b,c) \mapsto (a,-b,c)$ from $Q$ to itself. This induces a symmetry of $G$, preserving the coloring of edges but reversing their directions. Now, $(1,0,-p)$, corresponding to $x^2-p$, is fixed by $\sigma$, so $\sigma$ must take the cycle through $(1,0,-p)$ to itself. Call this cycle $C$. We consider two cases:

Case 1 $C$ has odd length, so the point antipodal to $(1,0,-p)$ is the midpoint of an edge. Let us suppose that it is an $E$-edge $(a,b,c) \to (a,-2a+b,a-b+c)$; the case of an $F$-edge is similar. Then $\sigma$ swaps $(a,b,c)$ and $(a,-2a+b,a-b+c)$, so we deduce $-b=-2a+b$ and $c=a-b+c$, implying $a=b$. Then $b^2-4ac = b(b-4c)=4p$. Since $b$ is even, $b-4c$ is as well, and the two factors are $2$ and $2p$; since $c<0$ we have $b=2$ and $b-4c=2p$, giving $c = (1-p)/2$. But then $GCD(a,b,c) = GCD(2,2,(1-p)/2)=2$ (using that $p \equiv 1 \bmod 4$) and contradicting our choice that $GCD=1$. We have a contradiction and deduce that we are instead in:

Case 2 $C$ has even length. Then the point $(a,b,c)$ antipodal to $(1,0,-p)$ must be fixed by $\sigma$, so $b=0$. Then $4a(-c) = 4p$ so $a(-c) = p$. We are looking for the solution that is not $(1,0,-p)$, so it must be $(p,0,-1)$. In short, we conclude that $G$ contains a path from $(1,0,-p)$ to $(p,0,-1)$. Moreover, the edge coming out of $(1,0,-p)$ is an $E$-edge and the edge into $(p,0,-1)$ is an $F$-edge, so we have $$(p,0,-1) = F^{a_{1}} E^{a_{2}} \cdots F^{a_{2r-1}} E^{a_{2r}} (1,0,-p)$$ for some positive integers $(a_1, a_2, \ldots, a_{2r})$.

Converting to roots of quadratics, $$\frac{1}{\sqrt{p}} = F^{a_{1}} E^{a_{2}} \cdots F^{a_{2r-1}} E^{a_{2r}} \left( \sqrt{p} \right).$$ We have $E^a(\lambda) = a+\lambda$ and $F^a(\lambda) = \frac{1}{a+\frac{1}{\lambda}}$. So $$\frac{1}{\sqrt{p}} = \frac{1}{a_1 +}\frac{1}{a_2 + } \cdots \frac{1}{a_{2r-1}+} \frac{1}{a_{2r}+\sqrt{p}}$$ or $$\sqrt{p} = a_1 + \frac{1}{a_2 + } \cdots \frac{1}{a_{2r-1}+} \frac{1}{a_{2r}+\sqrt{p}}.$$ We deduce that $$\sqrt{p} = [a_1, \overline{a_2, a_3, \ldots, a_{2r-1}, a_{2r}+a_1}].$$ The period is odd, as desired.

We can also use this result to solve the negative Pell equation. Let the Mobius transformation $F^{a_1} E^{a_2} \cdots F^{a_{2r-1}} E^{a_{2r}}(x)$ be equal to $\frac{ax+b}{cx+d}$. We have $$\frac{a \sqrt{p} + b }{c \sqrt{p} + d} = \frac{1}{\sqrt{p}}.$$ Using that $(a,b,c,d)$ are integers and $p$ is not square, we have $b=c$ and $d=ap$.

Since $\det \left( \begin{smallmatrix} a & b \\ c & d \end{smallmatrix} \right) = 1$, we deduce that $a^2 p - b^2 =1$ or, in other words, the negative Pell equation $b^2 - p a^2 = -1$ is solvable.

While we're at it, we can deduce more by also using the symmetry $\tau: (a,b,c) \mapsto (-c,b,-a)$. This swaps $(1,0,-p)$ and $(p,0,-1)$, and it reverses edge coloring and direction. So it reverses the path $(1,0,-p) \to \cdots \to (p,0,-1)$. Since $\tau$ switches edge coloring, it can not fix any edge, and we deduce that the mid point of the path must be a $\tau$ fixed vertex. We have $\tau(a,b,c) = (a,b,c)$ if and only if $a=-c$; in this case, $b^2 - 4 ac = b^2 + (2a)^2 = 4p$ and we deduce that $p = (b/2)^2 + a^2$ is a sum of squares.

Finally, since $\tau$ reverses the path, we deduce that $(a_1, a_2, \ldots, a_{2r})$ is a palindrome.