### Monday, October 20, 2008

## JSH: Explaining Pell's Equation

Oddly enough a clue that seals the explanation to Pell's Equation came up in arguments about my general solution to binary quadratic Diophantine equations, where it's spectacularly and to me, satisfyingly simple.

Essential to the argument is the simple relation that given x^2 + Dy^2 = F, it is also true that

(x-Dy)^2 + D(x+y)^2 = F*(D+1)

which allows you to generate a series of equations. But notice what happens with F=1, D=-3:

So that's

Key here is the requirement that

-D must be a quadratic residue modulo (D+1)^j

where j is a natural number giving the level into the series you are at minus 1, and if THAT IS NOT POSSIBLE, then factors of (D+1)^j must divide off and if all its factors divide off you can get a non-trivial solution.

So for D=-3, j=2, when (D+1)^j divides off completely, but for 7, you're looking at (-6)^j, and notice that factors of 2 routinely divide off, but the 3 is a hardy bugger, which hangs in there for some time, so you would look for when 7 is not a quadratic residue modulo 3^j (um, can someone give that answer? When is 7 not a quadratic residue modulo 3^j?).

So you really have to look by prime factors of D+1.

But then you have the explanation for why for some values of D you get solutions quickly while for others it can take a while as the mathematics is looking for when -D is NOT a quadratic residue modulo all the prime factors of D+1 raised to some even number power of j, so it dutifully goes along until it finds that situation and it can take a while.

Cool. I like explanations. So that number theoretic structure I call a Diophantine supermap is the key to understanding Pell's Equation and all its behavior.

Yeah, I knew it was important. Cool.

Essential to the argument is the simple relation that given x^2 + Dy^2 = F, it is also true that

(x-Dy)^2 + D(x+y)^2 = F*(D+1)

which allows you to generate a series of equations. But notice what happens with F=1, D=-3:

- x^2 - 3y^2 = 1
- (x+3y)^2 - 3(x+y)^2 = (-2)
- (4x+6y)^2 - 3(2x + 4y)^2 = (-2)^2

So that's

- x^2 - 3y^2 = 1
- (x+3y)^2 - 3(x+y)^2 = (-2)
- (2x+3y)^2 - 3(x + 2y)^2 = 1.

- 1^2 = 1
- (1)^2 - 3(1)^2 = (-2)
- (2)^2 - 3(1)^2 = 1

Key here is the requirement that

-D must be a quadratic residue modulo (D+1)^j

where j is a natural number giving the level into the series you are at minus 1, and if THAT IS NOT POSSIBLE, then factors of (D+1)^j must divide off and if all its factors divide off you can get a non-trivial solution.

So for D=-3, j=2, when (D+1)^j divides off completely, but for 7, you're looking at (-6)^j, and notice that factors of 2 routinely divide off, but the 3 is a hardy bugger, which hangs in there for some time, so you would look for when 7 is not a quadratic residue modulo 3^j (um, can someone give that answer? When is 7 not a quadratic residue modulo 3^j?).

So you really have to look by prime factors of D+1.

But then you have the explanation for why for some values of D you get solutions quickly while for others it can take a while as the mathematics is looking for when -D is NOT a quadratic residue modulo all the prime factors of D+1 raised to some even number power of j, so it dutifully goes along until it finds that situation and it can take a while.

Cool. I like explanations. So that number theoretic structure I call a Diophantine supermap is the key to understanding Pell's Equation and all its behavior.

Yeah, I knew it was important. Cool.