4
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Peter Feb 9 '17 at 18:33
  • $\begingroup$ 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. $\endgroup$ – Peter Feb 9 '17 at 18:34
  • $\begingroup$ @Peter there is a short proof for $a^2 - p b^2 = -1$ in Mordell's book Diophantine Equations. pages 55-56 $\endgroup$ – Will Jagy Feb 9 '17 at 18:46
  • $\begingroup$ @WillJagy Then please add this proof or at least the main idea to your answer. $\endgroup$ – Peter Feb 9 '17 at 18:47
  • $\begingroup$ @WillJagy Thank you, this completes the proof. $\endgroup$ – Peter Feb 9 '17 at 18:53
4
$\begingroup$

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
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.