Pell's equation with d congruent to 1 mod 4

Question

Currently in class we have seen a method for solving Pell's equation:

$$x^2 - dy^2 = 1$$

Using the facts: $$N_{K}(\alpha) = \pm1 \iff \alpha \in O_K^{X} \iff \alpha = \pm u^r $$

Where $u$ is the fundamental unit. However, I'm rather stumped as to how to proceed in solving the Pell's equation: $$x^2 - 13y^2 = -1$$

Because $d \equiv 1 \mod{4} $, so the ring of integers will take the form $\mathbb{Z}[\dfrac{1+\sqrt{13}}{2}]$ and so I can't view the equation as the norm of some unit in the ring of integers.

Is there a systematic way to proceed using these results or am I to explore different avenues? We haven't covered anything else beyond these results in relation to Pell's equation.

Answer 1

If $p \equiv 1 \pmod 4$ is a (positive) prime, there is always an integer solution to $x^2 - p y^2 = -1.$ The short proof is in Mordell, Diophantine Equations. The same proof gives the same conclusion for primes $p\equiv q \equiv 1 \pmod 4,$ Legendre symbol $(p|q) = -1,$ and $x^2 - pq y^2 = -1.$ I have probably posted both proofs on this site. There is no guarantee if $(p|q) = 1.$ The two smallest such failures are $x^2 - 205 y^2 \neq -1$ and $x^2 - 221 y^2 \neq -1.$

Actually finding such answers is simply finding the continued fraction for the square root of the $p$ or $pq$

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

Method described by Prof. Lubin at Continued fraction of $\sqrt{67} - 4$

$$ \sqrt { 13} = 3 + \frac{ \sqrt {13} - 3 }{ 1 } $$ $$ \frac{ 1 }{ \sqrt {13} - 3 } = \frac{ \sqrt {13} + 3 }{4 } = 1 + \frac{ \sqrt {13} - 1 }{4 } $$ $$ \frac{ 4 }{ \sqrt {13} - 1 } = \frac{ \sqrt {13} + 1 }{3 } = 1 + \frac{ \sqrt {13} - 2 }{3 } $$ $$ \frac{ 3 }{ \sqrt {13} - 2 } = \frac{ \sqrt {13} + 2 }{3 } = 1 + \frac{ \sqrt {13} - 1 }{3 } $$ $$ \frac{ 3 }{ \sqrt {13} - 1 } = \frac{ \sqrt {13} + 1 }{4 } = 1 + \frac{ \sqrt {13} - 3 }{4 } $$ $$ \frac{ 4 }{ \sqrt {13} - 3 } = \frac{ \sqrt {13} + 3 }{1 } = 6 + \frac{ \sqrt {13} - 3 }{1 } $$

Simple continued fraction tableau:
$$ \begin{array}{cccccccccccccccccccccccc} & & 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 } \\ \\ & 1 & & -4 & & 3 & & -3 & & 4 & & -1 & & 4 & & -3 & & 3 & & -4 & & 1 \end{array} $$

$$ \begin{array}{cccc} \frac{ 1 }{ 0 } & 1^2 - 13 \cdot 0^2 = 1 & \mbox{digit} & 3 \\ \frac{ 3 }{ 1 } & 3^2 - 13 \cdot 1^2 = -4 & \mbox{digit} & 1 \\ \frac{ 4 }{ 1 } & 4^2 - 13 \cdot 1^2 = 3 & \mbox{digit} & 1 \\ \frac{ 7 }{ 2 } & 7^2 - 13 \cdot 2^2 = -3 & \mbox{digit} & 1 \\ \frac{ 11 }{ 3 } & 11^2 - 13 \cdot 3^2 = 4 & \mbox{digit} & 1 \\ \frac{ 18 }{ 5 } & 18^2 - 13 \cdot 5^2 = -1 & \mbox{digit} & 6 \\ \frac{ 119 }{ 33 } & 119^2 - 13 \cdot 33^2 = 4 & \mbox{digit} & 1 \\ \frac{ 137 }{ 38 } & 137^2 - 13 \cdot 38^2 = -3 & \mbox{digit} & 1 \\ \frac{ 256 }{ 71 } & 256^2 - 13 \cdot 71^2 = 3 & \mbox{digit} & 1 \\ \frac{ 393 }{ 109 } & 393^2 - 13 \cdot 109^2 = -4 & \mbox{digit} & 1 \\ \frac{ 649 }{ 180 } & 649^2 - 13 \cdot 180^2 = 1 & \mbox{digit} & 6 \\ \end{array} $$

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

$$ \sqrt { 85} = 9 + \frac{ \sqrt {85} - 9 }{ 1 } $$ $$ \frac{ 1 }{ \sqrt {85} - 9 } = \frac{ \sqrt {85} + 9 }{4 } = 4 + \frac{ \sqrt {85} - 7 }{4 } $$ $$ \frac{ 4 }{ \sqrt {85} - 7 } = \frac{ \sqrt {85} + 7 }{9 } = 1 + \frac{ \sqrt {85} - 2 }{9 } $$ $$ \frac{ 9 }{ \sqrt {85} - 2 } = \frac{ \sqrt {85} + 2 }{9 } = 1 + \frac{ \sqrt {85} - 7 }{9 } $$ $$ \frac{ 9 }{ \sqrt {85} - 7 } = \frac{ \sqrt {85} + 7 }{4 } = 4 + \frac{ \sqrt {85} - 9 }{4 } $$ $$ \frac{ 4 }{ \sqrt {85} - 9 } = \frac{ \sqrt {85} + 9 }{1 } = 18 + \frac{ \sqrt {85} - 9 }{1 } $$

Simple continued fraction tableau:
$$ \begin{array}{cccccccccccccccccccccccc} & & 9 & & 4 & & 1 & & 1 & & 4 & & 18 & & 4 & & 1 & & 1 & & 4 & & 18 & \\ \\ \frac{ 0 }{ 1 } & \frac{ 1 }{ 0 } & & \frac{ 9 }{ 1 } & & \frac{ 37 }{ 4 } & & \frac{ 46 }{ 5 } & & \frac{ 83 }{ 9 } & & \frac{ 378 }{ 41 } & & \frac{ 6887 }{ 747 } & & \frac{ 27926 }{ 3029 } & & \frac{ 34813 }{ 3776 } & & \frac{ 62739 }{ 6805 } & & \frac{ 285769 }{ 30996 } \\ \\ & 1 & & -4 & & 9 & & -9 & & 4 & & -1 & & 4 & & -9 & & 9 & & -4 & & 1 \end{array} $$

$$ \begin{array}{cccc} \frac{ 1 }{ 0 } & 1^2 - 85 \cdot 0^2 = 1 & \mbox{digit} & 9 \\ \frac{ 9 }{ 1 } & 9^2 - 85 \cdot 1^2 = -4 & \mbox{digit} & 4 \\ \frac{ 37 }{ 4 } & 37^2 - 85 \cdot 4^2 = 9 & \mbox{digit} & 1 \\ \frac{ 46 }{ 5 } & 46^2 - 85 \cdot 5^2 = -9 & \mbox{digit} & 1 \\ \frac{ 83 }{ 9 } & 83^2 - 85 \cdot 9^2 = 4 & \mbox{digit} & 4 \\ \frac{ 378 }{ 41 } & 378^2 - 85 \cdot 41^2 = -1 & \mbox{digit} & 18 \\ \frac{ 6887 }{ 747 } & 6887^2 - 85 \cdot 747^2 = 4 & \mbox{digit} & 4 \\ \frac{ 27926 }{ 3029 } & 27926^2 - 85 \cdot 3029^2 = -9 & \mbox{digit} & 1 \\ \frac{ 34813 }{ 3776 } & 34813^2 - 85 \cdot 3776^2 = 9 & \mbox{digit} & 1 \\ \frac{ 62739 }{ 6805 } & 62739^2 - 85 \cdot 6805^2 = -4 & \mbox{digit} & 4 \\ \frac{ 285769 }{ 30996 } & 285769^2 - 85 \cdot 30996^2 = 1 & \mbox{digit} & 18 \\ \end{array} $$

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

$$ \sqrt { 205} = 14 + \frac{ \sqrt {205} - 14 }{ 1 } $$ $$ \frac{ 1 }{ \sqrt {205} - 14 } = \frac{ \sqrt {205} + 14 }{9 } = 3 + \frac{ \sqrt {205} - 13 }{9 } $$ $$ \frac{ 9 }{ \sqrt {205} - 13 } = \frac{ \sqrt {205} + 13 }{4 } = 6 + \frac{ \sqrt {205} - 11 }{4 } $$ $$ \frac{ 4 }{ \sqrt {205} - 11 } = \frac{ \sqrt {205} + 11 }{21 } = 1 + \frac{ \sqrt {205} - 10 }{21 } $$ $$ \frac{ 21 }{ \sqrt {205} - 10 } = \frac{ \sqrt {205} + 10 }{5 } = 4 + \frac{ \sqrt {205} - 10 }{5 } $$ $$ \frac{ 5 }{ \sqrt {205} - 10 } = \frac{ \sqrt {205} + 10 }{21 } = 1 + \frac{ \sqrt {205} - 11 }{21 } $$ $$ \frac{ 21 }{ \sqrt {205} - 11 } = \frac{ \sqrt {205} + 11 }{4 } = 6 + \frac{ \sqrt {205} - 13 }{4 } $$ $$ \frac{ 4 }{ \sqrt {205} - 13 } = \frac{ \sqrt {205} + 13 }{9 } = 3 + \frac{ \sqrt {205} - 14 }{9 } $$ $$ \frac{ 9 }{ \sqrt {205} - 14 } = \frac{ \sqrt {205} + 14 }{1 } = 28 + \frac{ \sqrt {205} - 14 }{1 } $$

Simple continued fraction tableau:
$$ \begin{array}{cccccccccccccccccccccc} & & 14 & & 3 & & 6 & & 1 & & 4 & & 1 & & 6 & & 3 & & 28 & \\ \\ \frac{ 0 }{ 1 } & \frac{ 1 }{ 0 } & & \frac{ 14 }{ 1 } & & \frac{ 43 }{ 3 } & & \frac{ 272 }{ 19 } & & \frac{ 315 }{ 22 } & & \frac{ 1532 }{ 107 } & & \frac{ 1847 }{ 129 } & & \frac{ 12614 }{ 881 } & & \frac{ 39689 }{ 2772 } \\ \\ & 1 & & -9 & & 4 & & -21 & & 5 & & -21 & & 4 & & -9 & & 1 \end{array} $$

$$ \begin{array}{cccc} \frac{ 1 }{ 0 } & 1^2 - 205 \cdot 0^2 = 1 & \mbox{digit} & 14 \\ \frac{ 14 }{ 1 } & 14^2 - 205 \cdot 1^2 = -9 & \mbox{digit} & 3 \\ \frac{ 43 }{ 3 } & 43^2 - 205 \cdot 3^2 = 4 & \mbox{digit} & 6 \\ \frac{ 272 }{ 19 } & 272^2 - 205 \cdot 19^2 = -21 & \mbox{digit} & 1 \\ \frac{ 315 }{ 22 } & 315^2 - 205 \cdot 22^2 = 5 & \mbox{digit} & 4 \\ \frac{ 1532 }{ 107 } & 1532^2 - 205 \cdot 107^2 = -21 & \mbox{digit} & 1 \\ \frac{ 1847 }{ 129 } & 1847^2 - 205 \cdot 129^2 = 4 & \mbox{digit} & 6 \\ \frac{ 12614 }{ 881 } & 12614^2 - 205 \cdot 881^2 = -9 & \mbox{digit} & 3 \\ \frac{ 39689 }{ 2772 } & 39689^2 - 205 \cdot 2772^2 = 1 & \mbox{digit} & 28 \\ \end{array} $$

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

$$ \sqrt { 221} = 14 + \frac{ \sqrt {221} - 14 }{ 1 } $$ $$ \frac{ 1 }{ \sqrt {221} - 14 } = \frac{ \sqrt {221} + 14 }{25 } = 1 + \frac{ \sqrt {221} - 11 }{25 } $$ $$ \frac{ 25 }{ \sqrt {221} - 11 } = \frac{ \sqrt {221} + 11 }{4 } = 6 + \frac{ \sqrt {221} - 13 }{4 } $$ $$ \frac{ 4 }{ \sqrt {221} - 13 } = \frac{ \sqrt {221} + 13 }{13 } = 2 + \frac{ \sqrt {221} - 13 }{13 } $$ $$ \frac{ 13 }{ \sqrt {221} - 13 } = \frac{ \sqrt {221} + 13 }{4 } = 6 + \frac{ \sqrt {221} - 11 }{4 } $$ $$ \frac{ 4 }{ \sqrt {221} - 11 } = \frac{ \sqrt {221} + 11 }{25 } = 1 + \frac{ \sqrt {221} - 14 }{25 } $$ $$ \frac{ 25 }{ \sqrt {221} - 14 } = \frac{ \sqrt {221} + 14 }{1 } = 28 + \frac{ \sqrt {221} - 14 }{1 } $$

Simple continued fraction tableau:
$$ \begin{array}{cccccccccccccccccc} & & 14 & & 1 & & 6 & & 2 & & 6 & & 1 & & 28 & \\ \\ \frac{ 0 }{ 1 } & \frac{ 1 }{ 0 } & & \frac{ 14 }{ 1 } & & \frac{ 15 }{ 1 } & & \frac{ 104 }{ 7 } & & \frac{ 223 }{ 15 } & & \frac{ 1442 }{ 97 } & & \frac{ 1665 }{ 112 } \\ \\ & 1 & & -25 & & 4 & & -13 & & 4 & & -25 & & 1 \end{array} $$

$$ \begin{array}{cccc} \frac{ 1 }{ 0 } & 1^2 - 221 \cdot 0^2 = 1 & \mbox{digit} & 14 \\ \frac{ 14 }{ 1 } & 14^2 - 221 \cdot 1^2 = -25 & \mbox{digit} & 1 \\ \frac{ 15 }{ 1 } & 15^2 - 221 \cdot 1^2 = 4 & \mbox{digit} & 6 \\ \frac{ 104 }{ 7 } & 104^2 - 221 \cdot 7^2 = -13 & \mbox{digit} & 2 \\ \frac{ 223 }{ 15 } & 223^2 - 221 \cdot 15^2 = 4 & \mbox{digit} & 6 \\ \frac{ 1442 }{ 97 } & 1442^2 - 221 \cdot 97^2 = -25 & \mbox{digit} & 1 \\ \frac{ 1665 }{ 112 } & 1665^2 - 221 \cdot 112^2 = 1 & \mbox{digit} & 28 \\ \end{array} $$

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

Answer 2

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

The viewpoint of real quadratic fields an norms of fundamental units is more concerned with $x^2 + xy - k y^2,$ where $4k+1 = pq$ in the second theorem. However, we showed above that the existence of a solution to $u^2 - (4k+1)v^2 = -1$ gives an immediate construction for a solution to $x^2 + xy - k y^2=-1,$ namely $x=u-v, y=2v.$

David Speyer reminded me of something Kap wrote out for me, years and years ago. From David's comments, I now understand what Kap was trying to show me. If $x^2 + x y - 2 k y^2 = -1,$ then $(2x+y)^2 - (8k+1)y^2 = -4. $ This is impossible $\pmod 8$ unless $y$ is even, in which case $(x + \frac{y}{2})^2 - (8k+1) \left( \frac{y}{2}\right)^2 = -1.$

There is more to it when we have $x^2 + x y - k y^2 = -1$ with odd $k.$ I wrote Kap's note in Buell, page 31. Take $$ u = \frac{ 2 x^3 +3 x^2 y + (6k+3)x y^2 + (3k+1)y^3}{2}, $$ $$ v = \frac{3 x^2 y + 3 x y^2 + (k+1)y^3}{2}. $$ $$ u^2 - (4k+1) v^2 = -1, $$ since $$ u^2 - (4k+1) v^2 = \left( x^2 + x y - k y^2 \right)^3. $$

...