Period of continued fraction of $\sqrt{p}$

Question

Few years ago, one of my friends find that $\sqrt{p}$ has periodic continued fraction with odd (resp. even) period iff $p\equiv 1(mod 4)$ (resp. $p\equiv 3(mod 4)$) for a prime $p$. (You can observe this in here : http://oeis.org/search?q=1%2C2%2C1%2C2%2C4%2C2%2C1%2C2%2C2%2C5%2C4%2C2%2C1%2C2%2C6%2C2&language=english&go=Search). However, I don't know any clues to prove this. He told that it may be related to Pell's equation. Do you have any ideas?

Answer 1

Yes. If prime $p \equiv 1 \pmod 4,$ there are both (nontrivial) solutions to $x^2 - p y^2 = 1$ and $u^2 - p v^2 = -1.$ If you keep track of the "convergents" $\frac{a}{b}$ while finding the continued fraction, you will actually find $a^2 - p b^2 = -1$ along the way, about halfway.

13

$$ \small \begin{array}{cccccccccccccccccccccccccccccc} & & 3 & & 1 & & 1 & & 1 & & 1 & & 6 & & 1 & & 1 & & 1 & & 1 & & 6 & \\ \frac{0}{1} & \frac{1}{0} & & \frac{3}{1} & & \frac{4}{1} & & \frac{7}{2} & & \frac{11}{3} & & \frac{18}{5} & & \frac{119}{33} & & \frac{137}{38} & & \frac{256}{71} & & \frac{393}{109} & & \frac{649}{180} & & \frac{4287}{1189} \\ \\ & 1 & & -4 & & 3 & & -3 & & 4 & & -1 & & 4 & & -3 & & 3 & & -4 & & 1 & & -4 \end{array} $$

29

$$ \sqrt {29} $$

$$ \scriptsize \begin{array}{cccccccccccccccccccccccccccccc} & & 5 & & 2 & & 1 & & 1 & & 2 & & 10 & & 2 & & 1 & & 1 & & 2 & & 10 & \\ \frac{0}{1} & \frac{1}{0} & & \frac{5}{1} & & \frac{11}{2} & & \frac{16}{3} & & \frac{27}{5} & & \frac{70}{13} & & \frac{727}{135} & & \frac{1524}{283} & & \frac{2251}{418} & & \frac{3775}{701} & & \frac{9801}{1820} & & \frac{101785}{18901} \\ \\ -29 & 1 & & -4 & & 5 & & -5 & & 4 & & -1 & & 4 & & -5 & & 5 & & -4 & & 1 & & -4 \end{array} $$

=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-==-=-=-=-=-=-=-=-=-=-=-=-=-=-=-==-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

THEOREM 1: With prime $p \equiv 1 \pmod 4,$ there is always a solution to $$ x^2 - p y^2 = -1 $$ in integers. The proof is from Mordell, Diophantine Equations, pages 55-56.

PROOF: Take the smallest integer pair $T>1,U >0$ such that $$ T^2 - p U^2 = 1. $$ We know that $T$ is odd and $U$ is even. So, we have the integer equation $$ \left( \frac{T+1}{2} \right) \left( \frac{T-1}{2} \right) = p \left( \frac{U}{2} \right)^2. $$

We have $$ \gcd \left( \left( \frac{T+1}{2} \right), \left( \frac{T-1}{2} \right) \right) = 1. $$ Indeed, $$ \left( \frac{T+1}{2} \right) - \left( \frac{T-1}{2} \right) = 1. $$

There are now two cases, by unique factorization in integers:

$$ \mbox{(A):} \; \; \; \left( \frac{T+1}{2} \right) = p a^2, \; \; \left( \frac{T-1}{2} \right) = b^2 $$

$$ \mbox{(B):} \; \; \; \left( \frac{T+1}{2} \right) = a^2, \; \; \left( \frac{T-1}{2} \right) = p b^2 $$

Now, in case (B), we find that $(a,b)$ are smaller than $(T,U),$ but $T \geq 3, a > 1,$ and $a^2 - p b^2 = 1.$ This is a contradiction, as our hypothesis is that $(T,U)$ is minimal.

As a result, case (A) holds, with evident $$p a^2 - b^2 = \left( \frac{T+1}{2} \right) - \left( \frac{T-1}{2} \right) = 1, $$ so $$ b^2 - p a^2 = -1. $$

$$ \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc $$

THEOREM 2: With primes $p \neq q,$ with $p \equiv q \equiv 1 \pmod 4$ and Legendre $(p|q)=(q|p) = -1,$ there is always a solution to $$ x^2 - pq y^2 = -1 $$ in integers. The proof is from Mordell, Diophantine Equations, pages 55-56.

PROOF: Take the smallest integer pair $T>1,U >0$ such that $$ T^2 - pq U^2 = 1. $$ We know that $T$ is odd and $U$ is even. So, we have the integer equation $$ \left( \frac{T+1}{2} \right) \left( \frac{T-1}{2} \right) = pq \left( \frac{U}{2} \right)^2. $$

We have $$ \gcd \left( \left( \frac{T+1}{2} \right), \left( \frac{T-1}{2} \right) \right) = 1. $$

There are now four cases, by unique factorization in integers:

$$ \mbox{(1):} \; \; \; \left( \frac{T+1}{2} \right) = a^2, \; \; \left( \frac{T-1}{2} \right) = pq b^2 $$

$$ \mbox{(2):} \; \; \; \left( \frac{T+1}{2} \right) = p a^2, \; \; \left( \frac{T-1}{2} \right) = q b^2 $$ $$ \mbox{(3):} \; \; \; \left( \frac{T+1}{2} \right) = q a^2, \; \; \left( \frac{T-1}{2} \right) = p b^2 $$ $$ \mbox{(4):} \; \; \; \left( \frac{T+1}{2} \right) = pq a^2, \; \; \left( \frac{T-1}{2} \right) = b^2 $$

Now, in case (1), we find that $(a,b)$ are smaller than $(T,U),$ but $T \geq 3, a > 1,$ and $a^2 - pq b^2 = 1.$ This is a contradiction, as our hypothesis is that $(T,U)$ is minimal.

In case $(2),$ we have $$ p a^2 - q b^2 = 1. $$ $$ p a^2 \equiv 1 \pmod q, $$ so $a$ is nonzero mod $q,$ then $$ p \equiv \left( \frac{1}{a} \right)^2 \pmod q. $$ This contradicts the hypothesis $(p|q) = -1.$

In case $(3),$ we have $$ q a^2 - p b^2 = 1. $$ $$ q a^2 \equiv 1 \pmod p, $$ so $a$ is nonzero mod $p,$ then $$ q \equiv \left( \frac{1}{a} \right)^2 \pmod p. $$ This contradicts the hypothesis $(q|p) = -1.$

As a result, case (4) holds, with evident $$pq a^2 - b^2 = \left( \frac{T+1}{2} \right) - \left( \frac{T-1}{2} \right) = 1, $$ so $$ b^2 - pq a^2 = -1. $$

$$ \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc $$

Caution: With primes $p \neq q,$ with $p \equiv q \equiv 1 \pmod 4$ and Legendre $(p|q)=(q|p) = 1,$ there may not be a solution to $$ x^2 - pq y^2 = -1 $$ For example, $205 = 5 \cdot 41$ and $221 = 13 \cdot 17.$ Below is the Lagrange-Gauss method for the continued fraction. No decimal accuracy is needed, no memory used in the computer.

jagy@phobeusjunior:~/old drive/home/jagy/Cplusplus$ ./Pell 205
0  form   1 28 -9   delta  -3
1  form   -9 26 4   delta  6
2  form   4 22 -21   delta  -1
3  form   -21 20 5   delta  4
4  form   5 20 -21   delta  -1
5  form   -21 22 4   delta  6
6  form   4 26 -9   delta  -3
7  form   -9 28 1   delta  28
8  form   1 28 -9

==========================================================

jagy@phobeusjunior:~/old drive/home/jagy/Cplusplus$ ./Pell 221
0  form   1 28 -25   delta  -1
1  form   -25 22 4   delta  6
2  form   4 26 -13   delta  -2
3  form   -13 26 4   delta  6
4  form   4 22 -25   delta  -1
5  form   -25 28 1   delta  28
6  form   1 28 -25