### Tuesday, March 31, 2009

## JSH: General alternate Pell's Equation result

I've noted several simple alternates to Pell's Equation, which includes the negative Pell's Equation, which allow solving the main one more easily, even with continued fractions, but that has been when D is a prime number.

Here is the general result which includes composite D:

Given D such that D=f_1*f_2, where the f's are positive integer factors and one of them can be 1, you have the following alternates to Pell's Equation with which you can solve it:

f_1*j^2 - f_2*k^2 = -1, where x = 2f_2*k^2 - 1 = 2f_1*j^2 + 1?

or

f_1*j^2 - f_2*k^2 = -2, where x = f_2*k^2 - 1 = f_1*j^2 + 1

or

f_1*j^2 - f_2*k^2 = 2, where x = f_2*k^2 + 1 = f_1*j^2 - 1

and x^2 - Dy^2 = 1.

One of those equations will be valid for each f_1, and f_2 available.

Here's an example with D=21:

3j^2 - 7k^2 = -1

I can multiply both sides by 3, and pull the 3 in with the j, so I have

(3j)^2 - 21k^2 = - 3

and notice that k=4, works if 3j = 9, so j=3, so x = 2*3*9 + 1 = 55,

and

55^2 - 21*12^2 = 1.

The alternates provide an easier route to solving Pell's Equation in general, as solutions for j tend to be approximately sqrt(x) of the solution for Pell's Equation, and continued fractions and other approaches known to Pell's Equation are available with the alternates.

So it's actually dumb to try and solve Pell's Equation directly!!!

You should use an alternate.

Here is the general result which includes composite D:

Given D such that D=f_1*f_2, where the f's are positive integer factors and one of them can be 1, you have the following alternates to Pell's Equation with which you can solve it:

f_1*j^2 - f_2*k^2 = -1, where x = 2f_2*k^2 - 1 = 2f_1*j^2 + 1?

or

f_1*j^2 - f_2*k^2 = -2, where x = f_2*k^2 - 1 = f_1*j^2 + 1

or

f_1*j^2 - f_2*k^2 = 2, where x = f_2*k^2 + 1 = f_1*j^2 - 1

and x^2 - Dy^2 = 1.

One of those equations will be valid for each f_1, and f_2 available.

Here's an example with D=21:

3j^2 - 7k^2 = -1

I can multiply both sides by 3, and pull the 3 in with the j, so I have

(3j)^2 - 21k^2 = - 3

and notice that k=4, works if 3j = 9, so j=3, so x = 2*3*9 + 1 = 55,

and

55^2 - 21*12^2 = 1.

The alternates provide an easier route to solving Pell's Equation in general, as solutions for j tend to be approximately sqrt(x) of the solution for Pell's Equation, and continued fractions and other approaches known to Pell's Equation are available with the alternates.

So it's actually dumb to try and solve Pell's Equation directly!!!

You should use an alternate.