Are there Pell Equations $x^2 - dy^2 = n$ that are easy to solve?

Question

Consider the Pell equation $x^2 - dy^2 = n$ where $d$ is a positive non-square integer.

Are there examples of special $d$ that makes it easy to solve (obtain non-trivial solutions) the equation for any $n \in Z - \{ 0 \} $?

Note: To clarify the motivation behind this question, I have $n$ that needs to be represented in a Generalized Pell Equation form $(x^2 - dy^2)$. If we can freely choose $d$ positive non-square, can we make choice(s) for $d$, perhaps depending on $n$ (since some choices of $d$, $n$ do not permit solutions), that renders the equation easily solvable.

See related: Is every integer $z$ representable in Pell form as $x^2 \pm dy^2 =z$?

Answer 1

I developed a single variable function that generates Pell numbers in sequence.

\begin{equation}\quad m=k+\sqrt{2k^2+(-1)^k}\end{equation} Beginning with zero, each value of $k$ generates an integer $m$ which is the next Pell number. Here are samples (beginning with $1$) I used to generate Pythagorean triples where $B=A\pm1$. \begin{align*} k=1\quad &\implies m=(1+\sqrt{2(1)^2+(-1)^1}\space)\big)=2\quad & F(2,1)=(3,4,5)\\ k=2\quad &\implies m=(2+\sqrt{2(2)^2+(-1)^2}\space)\big)=5\quad & F(5,2)=(21,20,29)\\ k=5\quad &\implies m=(5+\sqrt{2(5)^2+(-1)^5}\space)\big)=12\quad & F(12,5)=(119,120,169)\\ k=12\quad &\implies m=(12+\sqrt{2(12)^2+(-1)^{12}}\space)\big)=29\quad & F(29,12)=(697,696,985) \end{align*}

Alternatively, you can generate a Pell number $(P)$ directly using this formula. \begin{equation} P_n= \frac{(1 + \sqrt{2})^n - (1 - \sqrt{2})^n}{2\sqrt{2}}\qquad n\ge0 \end{equation}

It will yield $\quad P_0=0\quad P_=1\quad P_2=2\quad P_3=5\quad P_4=12\quad P_5=29\quad P_6=70\quad ...$

This is the second formula after the line reading "proved using telescoping series" in the Pell numbers link above and it seems to be the easiest to use of the ones I've tried.

Answer 2

This is called the generalized Pell equation. As in the classical case there is an algorithm, based on simple continued fractions, due to Lagrange, which solves $$ x^2-dy^2=n $$ for any given squarefree $d$ and given $n\in \Bbb Z\setminus \{0\}$.

Reference: Section $6$ of Keith Conrad's notes.

I would not call this algorithm "trivial" but certainly it is well-known and easy to perform. For small $d$, like $d=2$ it might be a bit quicker, but still is non-trivial.

Answer 3

For any particular $d$ there are theorems that tell you which values of $n$ are representable. See https://en.wikipedia.org/wiki/Binary_quadratic_form .

In particular, when $d=-1$ a prime $n$ is a sum of squares if and only if it's congruent to $1$ modulo $4$. Even in that simplest of cases finding the squares that sum to $n$ isn't easy: see https://stackoverflow.com/questions/5380323/whats-the-fastest-algorithm-to-represent-a-prime-as-sum-of-two-squares .

So the answer to your question is "no".

Answer 4

You can answer in the negative if you can show that $n$ is not a perfect square, modulo $d.$ This is easier to do if you can prime factorize $d.$ if not, you can only use the Jacoby symbol, which, if it returns $-1,$ proves that $n$ is not a square modulo $d,$ but a value of $1$ doesn't mean it is.

---

When $n>0,$ you can find a maximum $x$ to check, and solve the problem in finite time.

First solve for $a^2-db^2=1$ for smallest integer $a\geq 1$ and the corresponding positive $b.$

Then if $$x^2-dy^2=n\tag{1}$$ has a solution, it has a solution with: $$x\leq \sqrt{\frac{n(a+1)}{2}}$$

This is because if $(x,y)$ is a positive solution to (1), then so is $(xa-ydb,ay-xb).$

Now, if $-x<xa-ydb<x$ then we have a solution for a smaller positive $x.$ And that happens if:

$$x(a+1)>ydb>x(a-1)$$

All terms are positive, so we can square both side:

$$x^2(a+1)^2>y^2d^2b^2>x^2(a-1)^2$$

Substituting $dy^2=x^2-n$ you get:

$$x^2(a+1)^2>db^2(x^2-n)>(a-1)^2x^2.$$

Now, $db^2=a^2-1.$ Subtracting $db^2x^2$ from both sides gives you:

$$x^2(2a+2)>-n(a^2-1)>(2-2a)x^2.$$

Since $x^2(2a+2)$ is always positive, and $-n(a^2-1)$ is negative, the first inequality is always true.

So if $$\frac{n(a+1)}2=\frac{n(a^2-1)}{2(a-1)}<x^2$$ then we can find a smaller positive $x.$

So if there is a solution, there must be a solution with $$2\leq x \leq\sqrt{\frac{n(a+1)}{2}}$$

---

I think, for $n<0$ you can show there must be a solution with:

$$2\leq x \leq \sqrt{\frac{-n(a-1)}2}$$

---

Of course, $a$ can be very large. When $d=97,$ $a= 1766319049.$

---

It's actually easier to check $y.$ You only have to check:

$$1\leq y\leq\sqrt{\frac{n(a-1)}{2d}}$$ when $n>0,$ and

$$1\leq y\leq\sqrt{\frac{-n(a+1)}{2d}}$$ when $n<0.$