3
$\begingroup$

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$?

$\endgroup$
7
  • 1
    $\begingroup$ Are you aware that you are asking for a trivial way to obtain non-trivial solutions (if we look at both title and body of your question)? $\endgroup$ – user436658 Sep 23 '20 at 14:48
  • $\begingroup$ $d$ is non-square. $d = 1$ in the given equation is equivalent to factoring $n$ which in itself is not trivial. $\endgroup$ – vvg Sep 23 '20 at 16:27
  • $\begingroup$ @SI - I've edited the question to align it with textbook GPE definition. $\endgroup$ – vvg Sep 23 '20 at 17:00
  • $\begingroup$ @vvgiri I appreciate being given the "correct" checkmark but if you do not do anything more, the bounty will go to the answer with most upvotes of 2 or more. $\endgroup$ – poetasis Oct 2 '20 at 17:24
  • $\begingroup$ @poetasis - I've already upvoted your answer. Thanks for your response as it helped me with my problem. $\endgroup$ – vvg Oct 2 '20 at 17:27
1
+50
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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".

$\endgroup$
1
$\begingroup$

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.$

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