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

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?

• The equation $a^2-Nb^2=-1$ has a solution if and only if the period length of the continued fraction of $\sqrt{N}$ is odd. The equation $a^2-pb^2=-1$ cannot be solved if $p\equiv 3\mod 4$ because that would imply that $-1$ is a quadratic residue modulo $p$, which is not the case. – Peter Feb 9 '17 at 18:33
• Unfortunately, I do not have an idea how to show that $a^2-pb^2=-1$ has always a solution for $p\equiv 1\mod 4$, which is all we need. – Peter Feb 9 '17 at 18:34
• @Peter there is a short proof for $a^2 - p b^2 = -1$ in Mordell's book Diophantine Equations. pages 55-56 – Will Jagy Feb 9 '17 at 18:46
• @WillJagy Then please add this proof or at least the main idea to your answer. – Peter Feb 9 '17 at 18:47
• @WillJagy Thank you, this completes the proof. – Peter Feb 9 '17 at 18:53

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