Connecting Diophantine hyperbola to ellipse

The equation x² - Dy² = 1 has a direct Diophantine connection to an ellipse for a special case.

The ellipse is:  (D-1)j² + (j +1)² = (x+y)²  where  j = ((x+Dy)-1)/D, when x = 1 mod D.

Or:  (D-1)j² + (j -1)² = (x+y)²  where j = ((x+Dy)+1)/D, when x = -1 mod D.

So the special case is x = 1 mod D or -1 mod D, which must be true if D is a prime or twice a prime, but the connection will exist whenever x meets the conditions.

Proof:

Using my method to reduce binary quadratic Diophantine equations on x² - Dy² = 1, gives:

(x+Dy)² - D(x+y)² = -(D-1)

(If you multiply out and simplify you simply return to x² - Dy² = 1.)

Shifting things around a bit, I have:

(x+Dy)² + (D-1) = D(x+y)²

And I can group to divide off D:

[(x+Dy)² - 1]/D + 1 = (x+y)²

Now we'll shift to the special case of x = 1 mod D or x = - 1 mod D.

Introducing integer j, I have x+Dy = jD +/- 1, and only one of those cases will be true. That usage is to keep from writing x+Dy = jD + 1 or x+Dy = jD - 1, over and over again.

And making that substitution gives:

[(jD +/- 1)² - 1]/D + 1 = (x+y)²

And squaring and simplifying a bit gives:

Dj² +/- 2j + 1 = (x+y)²

So now I just subtract and add j² so that I can complete the square to get:

(D-1)j² + (j +/- 1)² = (x+y)²

And you have your ellipse.

Proof complete.

Here is an example of the result with the famous case of D=61:

1766319049² - 61(226153980)² = 1

x = 1766319049, y = 226153980, and x = 1766319049 = -1 mod 61, so the second equations apply.

(D-1)j² + (j - 1)² = (x+y)², j = (x+Dy+1)/D

Which gives j = 255110030.

60*255110030² + 255110029² = 1992473029²

If you'd like to continue further, additional research shows you can now generate yet another hyperbola from the ellipse.


James Harris

A Math Mystery Resolved

The equation x² - Dy² = 1 has one of the weirdest stories in mathematics, with a convoluted history that goes back thousands of years, and the story just keeps getting stranger.

I like to call it the two conics equation because in rationals it gives you hyperbolas or ellipses depending on the sign of D, while mathematicians like to consider it only with integers and call it Pell's Equation, but then say that John Pell doesn't deserve that credit.

But they also seem to fail to mention that there was a mystery in the relation between D and the size of the fundamental solution, which is the first non-zero integer solution.  And that's kind of a BIG DEAL as without that explanation the equation can seem to be a little crazy.

For instance, with D=2, it's nice and sweet with a nice and easy fundamental solution:  3² - 2(2)² = 1

And it's hard to see easier than that!  Though you often do see other solutions that are easy.  And lots of them.

But then you have ones that are hard where the fundamental solution is huge, where the most famous one because Fermat used it as a challenge problem--yeah, this equation is old and was even old when he played with it--is for the D=61 case.

1766319049² - 61(226153980)² = 1

But is immediately followed by an easy one: 63² - 62(8)² = 1

But why?  Some may know that if D+2 is a square you get easy solutions from an identity, but I can go a little further to D=72, and you get the easy:  17² - 72(2)² = 1

Now that's just damn strange.

And if you wish you can go to a page on MathWorld where they conveniently list the solutions for D to 102--go down to the bottom half of the page to see them.  They skip squares as D can't be a square, since (x - sqrt(D)y)(x + sqrt(D)y) = 1.

If you see a pattern there, then you should congratulate yourself, as then you figured out the rules!

And here they are solving an ancient math mystery:

1. If D is prime or twice a prime, solutions will tend to be larger, where that is because x = 1 mod D or -1 mod D, for those cases.

2. The more small prime factors of D-1, the larger solutions will tend to be.

3. If D is prime or twice a prime or for any other reason x = 1 mod D or -1 mod D, and D-1 has a lot of prime factors, and especially if 4 is a factor then solutions are the largest of all, unless D-1, D+1, D-2, or D+2 is a square, as then solutions will tend to be small regardless, as a sort of release valve kicks in for those special cases.

So if you figured that out then you managed to see something that I managed to prove September, when I finally got them right as for a while I missed the x = 1 mod D or -1 mod D thing for reasons that still escape me.  

So now you know what Fermat didn't know, and if he had known then he'd have invented modular arithmetic, which he could have done, but history says he didn't and modular arithmetic didn't emerge fully until the 1800's and Gauss had a lot to do with that emergence.

Such a cool story.  I love mentioning those names.

So today we're in the 21st century and those rules are backed by a really cool proof, which isn't very formal now as you can say, it's still at first draft as I just figured everything out.  Polishing up math proofs takes time, and motivation.  For now I'd like to get some attention to the result!  Then can make it all pretty.

And it should be easy to get attention here.  Math people didn't even realize there was a mystery, apparently mostly deciding that what they call Pell's Equation was just crazy, and it bounced around with D for no particular reason at all!  Since they call it Pell's Equation and then say John Pell doesn't deserve credit, maybe they just think crazy goes with the thing.


James Harris

Generalizing quadratic Diophantine

Using an alternate form from x² - Dy² = F, I can generalize as follows.

(z-ky)² - Dy² = F

Expand out:

z² - 2kyz + k²y² - Dy² = F

Now obviously, it makes sense to group the y², and see:

z² - 2kyz - (D-k²)y² = F, which is also z² - 2kyz - F = (D-k²)y², which requires that 2kyz + F = -1 or 1 mod 8, or 0 mod 4.

And now for what is an amazing trick, which only arrived with modular arithmetic, as before, to mathematicians who did not have it, the above would be pointless.

They literally could not see what happens next:

z² - 2kyz = F mod D-k²

And now you can move that F to the left hand side:

z² - 2kyz - F = 0 mod D-k²

And solve for y, to find:

2y = (kz)^-1(z² - F) mod D-k²

which is also:

2y = k^-1(z - Fz^-1) mod D-k²

Turns out that I need one more equation.

Going back to: (z-ky)² - Dy² = F

Let's add k²y² to both sides: (z-ky)² + k²y² - Dy² = k²y² + F

and now again focusing mod D-k², I have:

(z-ky)² = k²y² + F mod D-k²

And I have what I like to call a quadratic residue engine, which then is as follows.

Given (z-ky)² - Dy² = F, if integer solutions for a chosen k exist, it must be true that:

2y = k^-1(z - Fz^-1) mod D-k²

(z-ky)² = k²y² + F mod D-k²

where 2kyz + F = -1 or 1 mod 8, or 0 mod 4, if D-k² is a square.

Giving solutions for: x² - Dy² = F mod D-k²


James Harris

A Neat Trick

The idea that modern advances in knowledge can greatly enhance and simplify is potent in just about every field of human endeavor and is fun for the amateur math researcher, where I can use a neat trick only available with modular arithmetic.

Consider x² - Dy² = 1, where mathematicians like to study it as a Diophantine equation, which means you try to find integer solutions, and in its case you look for nonzero ones instead of the trivial case where y=0. Nonzero integer solutions are called the fundamental solution and the equation is called Pell's Equation, in honor of John Pell, though oddly enough mathematicians also say he doesn't deserve it.

People have studied the equation for thousands of years, but modular arithmetic has been around for a lot shorter time, so a nifty solution was not possible until the time of Gauss, where I will shift its form to use a neat trick:

(z-y)² - Dy² = 1

Expand out:

z² - 2yz + y² - Dy² = 1

Now obviously, it makes sense to group the y², and see:

z² - 2yz - (D-1)y² = 1

And I've talked about this before in other posts, but zipped past what is an amazing trick, which only arrived with modular arithmetic, as before, to mathematicians who did not have it, the above would be pointless.

They literally could not see what happens next:

z² - 2yz = 1 mod D-1

And now you can move that 1 to the left hand side: z² - 2yz - 1 = 0 mod D-1

And solve for y, to find:

2y = z^-1(z² - 1) mod D-1

Without a way to solve for y modularly--as it hadn't been invented yet--previous math people found various clever ways to get solutions. And if you read about "Pell's Equation" on the web you can get a lot of history lessons on what they did, while I just solved it modularly, very quickly.

Now a modular solution is not necessarily an explicit answer, but the technique given can be generalized, with another variable, I'll call k:

(z-ky)² - Dy² = 1

Which gives from the same steps above:

2y = (kz)^-1(z² - 1) mod D-k²

which can also be written as:

2y = k^-1(z - z^-1) mod D-k²

where you also get an added rule, as z² - 2kyz - 1 = (D-k²)y², shows that D-k² cannot be a square, if k is even.

Notice that k and z are forced to be coprime to D-k² so that the modular inverses exist.

Turns out that I need one more equation.

Going back to: (z-ky)² - Dy² = 1

Let's add k²y² to both sides: (z-ky)² + k²y² - Dy² = k²y² + 1

and now again focusing mod D-k², I have:

(z-ky)² = k²y² + 1 mod D-k²

And I have what I like to call a quadratic residue engine, which then is as follows.

Given (z-ky)² - Dy² = 1, it must be true that:

2y = k^-1(z - z^-1) mod D-k²

(z-ky)² = k²y² + 1 mod D-k²

when if k is even, D-k² is not a square.

Now you can get as many modular solutions for y as you want, and use them to get answers for y with something called the Chinese remainder theorem.

While I will not work it all the way through, it may help to get a sense of how it might work with a famous large case, which is D=61, which I looked up on the web to find that x = 1766319049, y = 226153980.

1766319049² - 61*226153980² = 1

Let's start with k=1, and notice that 2y = (z - z^-1) mod 60, requires that z be coprime to 60 so that its modular inverse exists, which means that z can only be: 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 49, 53, or 59.

But the second equation show things are even simpler than that might indicate:

(z-y)² = y² + 1 mod 60, which requires that y=0 mod 60 or you need a quadratic residue that when 1 is added to it, is STILL a quadratic residue, which is called a quadratic residue pair, of which there is only one modulo 60, as here are all the quadratic residues modulo 60:

1, 4, 9, 16, 21, 24, 25, 36, 40, 45, 49

So we know that y² = 0 mod 60 or y² = 24 mod 60, so despite having 14 possible z's, there are only a few possible answers for y. And since we have the fundamental answer it's easy enough to see that 30 is in fact a factor of 226153980.

The curious might wonder with 2y = (z - z^-1) mod 60, with all the possible z's, how many cases for y=0 come up.

Those cases for z are: 11, 19, 29, 31, 41, 49, 59, where for all those y² = 0 mod 60.

(Intriguingly, for all the other cases the modular inverse of z is a prime number, which I'm not sure is significant.)

So you could have two possibilities for y mod 60, since for y² = 24 mod 60, you'd only need one answer, and then can go on to other values by shifting k. But notice that 2 and 3 are definitely factors of y. So fewer possibilities with, k=2, as then you're modulo 57, where you know that 3 has to be a factor of y. And the quadratic residues modulo 57 are:

1, 4, 6, 7, 9, 16, 19, 24, 25, 28, 30, 36, 39, 42, 43, 45, 49, 54, 55

And each possible y is indeed forced to have 3 as a factor.

At k=3, you have modulo 52, which has for quadratic residues:

1, 4, 9, 12, 13, 16, 17, 25, 29, 36, 40, 48, 49

And at k=4, you are modulo 45, which has for quadratic residues:

1, 4, 9, 10, 16, 19, 25, 31, 34, 36, 40

That again shows 3 is a factor and gives 5 a choice, as y² = 0 mod 45 is possible.

It is of interest that the k=6 case is blocked because k is even and 61 - 36 = 25, which is a square. That case has no quadratic residue pairs and if not blocked would falsely indicate that 5 must be a factor of y.

And still a long ways away from getting the actual answer for y, which is HUGE, but intriguingly enough, there is a short-cut, which in this case is to use m² - 61n² = -1, which has a solution here, as all the tricks above work with it, though the equations shift a bit.

It gives a solution to "Pell's Equation" from: x = 2m² + 1.

For instance,

29718² - 61*3805² = -1, so m = 29718, gives

x = 1766319049, from x = 2m² + 1

Notice the k=6 case is valid here as the rule that D-k² cannot be a square if k is even doesn't apply and 5 gets forced as a factor. The curious reader can see how things shift for the other factors. I looked the answer up here as well, but 3805 is a lot more accessible so probably could have calculated that if I were interested in the effort.

With D a prime, if m² - Dn² = -1 doesn't have solutions then the other alternate equations m² - Dn² = -2 or m² - Dn² = 2, will, where again their answers are much smaller.

Lots of fun things then thanks to the advance called modular arithmetic, which allows you to just solve for y modularly, where without it, things are not so easy.

And possibly new ways to approach getting explicit answers where I just glanced at the surface of what is to me a less interesting issue, as people have ways of getting those now using other techniques.


James Harris

Two Conics Equation Solutions

Solving for modular solutions to x² - Dy² = 1, is surprisingly easy, with an alternate form. Consider

(z-y)² - Dy² = 1

as then z² - 2zy + y² - Dy² = 1, so I can group to find D-1 makes an appearance:

z² - 2zy - (D-1)y² = 1, so z² - 2zy - 1 = (D-1)y²

And then solve for y modulo D-1, to find:

2y = z^-1(z² - 1) mod D-1

So what is z? Well it is a residue of D-1, and intriguingly, the implication is that for every such residue except the trivial z = 1 mod D-1, if that residue is allowed, since the modular inverse blocks cases where z and D-1 share prime factors, then there is a solution for the original equation, which mathematicians commonly call Pell's Equation. I like to call it the two conics equation, as it gives hyperbolas or ellipses depending on the sign of D, though for integer solutions only, D is positive so you're considering hyperbolas.

Surprisingly if you do a search on "Pell's Equation" it does not appear that mathematicians noticed that you can so easily solve for y modularly, but it's not always clear that something is previously unknown for that reason. And it turns out that knowing y mod D-1 does not mean you have an explicit solution, as it can be greater than D-1.

However, I have also shown this result pushes rules upon quadratic residue pairs, which allows you to count them. And that's just one thing that I noticed quickly. Who knows how many ways this result impacts number theory at this point, but that is enough to suggest it was previously unknown.

And since I gave the rules for fundamental solutions to x² - Dy² = 1, it seems likely to me that not having a way to prove those--though they may have guessed them--mathematicians did not know how to solve for y modularly either.

But it gets better as generalizing may pull in explicit solutions of any size.

Consider now adding yet another variable k.

(z-ky)² - Dy² = 1

Then we solve to find:

2y = (kz)^-1(z² - 1) mod D-k²

So you can just find a series of values for y modulo a succession of values by shifting k, and since D can be less than k², you have as many as you wish. And then you just use the Chinese remainder theorem to get an ever larger value for y, but how do you pick?

Well I'm not sure as I just had this idea but the math may not care, and may give you a solution regardless of which residues you use, which just may not be the fundamental solution. But that is just a conjecture at this point.

One way of considering it is there are an infinity of y's that will work, so your arbitrary pick of residues may be like dialing up one of them.

But if true it is a way to solve the original equation trivially at will, and you can work back from a larger solution to the fundamental solution if you really want it.

Intriguingly, these results also push against quadratic residues here as well, and who knows what the full impact is.


James Harris

Two Conics Equation Modular Solutions

It is weird to try and absorb just how much was missed with x² - Dy² = 1, by mathematicians, when it is one of their most famous equations. They call it Pell's Equation, and then say John Pell doesn't deserve that honor, so recently I began calling it the two conics equation.

But even weirder than the name thing, consider a few things they missed.

Turns out you can just solve for modular solutions really easily, by using a different form.

(n-m)² - Dm² = 1

So now m = y or m = -y from the original, but then n = x+y or n = x-y.

From that format we can now focus on D-1:

n² - 2mn - 1 = (D-1)m²

which is:

n² - 2mn - 1 = 0 mod D-1

And I can just solve for m: 2m = n^-1(n² - 1) mod D-1

I've left the 2 on the left-hand side because if D-1 is even, you'd divide it off, while n must be coprime to D-1, which means not share any prime factors, because of the modular inverse.

So you have as a modular solution for x² - Dy² = 1 that:

2y = n^-1(n² - 1) mod D-1

Wow, that was easy.

Here's an example, where I know n from working back from a solution for D=38.

With n=6, I have:

2y = 6^-1(6² - 1) mod 37 = 31*(36-1) mod 37 = 12 mod 37

So I get y = 6 mod 37, and with this picked example 37² - 38(6)² = 1.

Of course one problem is it doesn't necessarily give you the smallest non-trivial integer solution, which is called the fundamental solution, but it is still of interest.

Maybe I shouldn't move too quickly from how remarkable the solution is. It is an answer which solves the equation modularly. And it shows a powerful role for the difference between a number and its modular inverse as of course that is also:

2y = n - n^-1 mod D-1

That even remarkably has implications for quadratic residues!

So it is a stunning result, with a huge reach across number theory.

So x² - Dy² = 1 has an easy and beautifully simple modular solution modulo D-1.

But also that is just very, very strange that it's not part of the known accepted literature, as my research is on the fringe. I'm not an establishment source. And this equation is HUGE in number theory. It's an extremely famous equation for mathematicians. And I've looked up "Pell's Equation" on the web lots of times, gone to link after link after link, and never seen even a clue that you could solve it modularly so easily. Very, very weird.

And this approach works on alternate forms, like:

(n-m)² - Dm² = -1

n² - 2mn + 1 = (D-1)m²

which is: n² - 2mn + 1 = 0 mod D-1

And I can just solve for m: 2m = n^-1(n² + 1) mod D-1

So easily enough for (n-m)² - Dm² = 2, I have: 2m = n^-1(n² - 2) mod D-1

And finally, for (n-m)² - Dm² = -2, I have: 2m = n^-1(n² + 2) mod D-1

Those alternate forms if they have solutions actually lead to solutions for the original x² - Dy² = 1, but they may not have solutions. For instance each requires a quadratic residue, for instance (n-m)² - Dm² = -1, cannot have integer solutions if -1 is not a quadratic residue modulo D.

These results are not just minor curiosities either, as solutions for the alternate forms of the two conics equation tend to be smaller by roughly a square. So answers are approximately the square root of solutions to the original, and if m is less than D-1 for a solution then you get it simply handed to you.

But it gets better. I've proven that what I call a quadratic residue engine leads to a way to count quadratic residue pairs. So this path leads to results on quadratic residues, which is just extraordinary.

So how about the alternates? Here are their corresponding quadratic residue engines:

1. (n-m)² - Dm² = -1

2m = n^-1(n² + 1) mod D-1, (n - m)² = m² - 1 mod D-1


2. (n-m)² - Dm² = 2

2m = n^-1(n² - 2) mod D-1, (n - m)² = m² + 2 mod D-1


3. (n-m)² - Dm² = -2

2m = n^-1(n² + 2) mod D-1, (n - m)² = m² - 2 mod D-1


And each gives quadratic residue results when they have solutions, and I should note that the equations above are valid when fundamental solutions exist, which for instance in all cases excludes D a perfect square. But for the original two conics equation that is the only exclusion, while for the alternates there are others.

So not as powerful as the original, which for instance, gives a way to count quadratic residue pairs for all primes, but still intriguing, as when those equations hold sway they will force quadratic residues to have certain patterns.

The first, of course, just gives quadratic pairs again, but the other two force some quadratic residues to be 2 away from each other, and one wonders how different values impact, as of course I could keep going with alternates, but chose the minimum three necessary to cover the range of solutions to the original two conics equation, as again I'll mention that to solve the original, you can instead solved the alternates. To see me discuss that more you can go to an earlier post.

So the equation x² - Dy² = 1 still had quite a few surprises left with elementary results in easy reach, including the ability to just solve the thing modulo D-1, which is just extraordinary.

How were these results missed before? I can only speculate, but maybe with so much history and the tendency of mathematicians to revere the past, along with known methods for solving it, people just didn't keep playing with the thing. But again, I'm only speculating.

But that left some truly beautiful results for me to stumble across and I can only marvel at the oddity of the situation, and consider how lucky I am.

These results presumably should have been found over a hundred years ago.


James Harris

Counting quadratic residue pairs

The story of x² - Dy² = 1 revealed yet another twist a few days ago when I realized I could count quadratic residue pairs, with what I call a quadratic residue engine, revealed by using its alternate form (n-m)² - Dm² = 1.

The quadratic residue engine is simple enough:

2m = n^-1(n² - 1) mod D-1

(n - m)² = m² + 1 mod D-1

And it shows how quadratic residue pairs--which I hadn't thought about until a few days ago--are actually often forced to occur, with the ability also to count them.

That is just amazing for a supposedly well researched equation, as mathematicians tend to call x² - Dy² = 1, Pell's Equation, and then tell you John Pell doesn't deserve that credit, but also they say it is well studied. Clearly they are wrong.

A quadratic residue result is HUGE and is such a giant thing in number theory that there is no way they had a clue that "Pell's Equation" lead to a key result on quadratic residue pairs. And I doubt they'd have kept the wrong attribution if the importance of the equation were well-known.

Now to math, and for those curious about what a quadratic residue pair looks like, here's a list of quadratic residues for 31:

1, 2, 4, 5, 7, 8, 9, 10, 14, 16, 18, 19, 20, 25, 28

And there are 7 pairs: {1,2}, {4,5}, {7,8}, {8,9}, {9,10}, {18,19}, {19, 20}

And that count is given by: floor((31 - 1)/4) = 7

In general for odd prime p, the count of quadratic residue pairs is:

floor((p-1)/4), if p mod 4 = -1, or

(p-5)/4 if p mod 4 = 1.

And with the first to remove the floor you can just use (p-3)/4.

Deriving those results is surprisingly easy.

One important initial result is that with

2m = n^-1(n² - 1) mod D-1

if D-1 is prime there is a unique m for each unique {n, n^-1} pair.

Proving it is easy, as consider n and n', such that:

2m = n^-1(n² - 1) = n'^-1(n'² - 1) mod D-1

Then:

n'*n² - n' = n*n'² - n mod D-1, so

n'*n² - n*n'² = n' - n mod D-1, and:

n'*n(n - n') = n' - n mod D-1, and if n - n' is coprime to D-1 you get finally n'*n = -1 mod D-1, or n' = -n^-1 mod D-1. The coprimeness requirement is fulfilled if D-1 is prime as no difference of residues can equal the modulus.

Now notice that multiplying the modular inverse through with 2m = n^-1(n² - 1) mod D-1, gives:

2m = n - n^-1 mod D-1

So with n', you have 2m = n' - n'^-1 = -n^-1 + n mod D-1

So each n is associated uniquely with m, when D-1 is prime.

Now consider D-1 to be a prime p. Then there are p-1 residues, but n has a unique modular inverse so there are only (p-1)/2 unique m's. But half of those are -m mod D-1, so you again divide by 2 to give approximately (p-1)/4.

But if p mod 4 = 1, it's also possible that m² = -1 mod D-1.

And in that case one is removed, so (p-1)/4 - 1 = (p-5)/4

That one case can be seen with p = 29:

1, 4, 5, 6, 7, 9, 13, 16, 20, 22, 23, 24, 25, 28

Which has 6 quadratic residue pairs as required.

Intriguingly the principle can be used to count residue pairs for other than primes, as long as D is not a square. But you wouldn't have the full residue count to start like before because n must be coprime to D-1.

And from the count of available n's two different m's can work with:

(n - m)² = m² + 1 mod D-1

Then of course m'² = m² mod D-1, requires that D-1 be composite, if m does not equal m' or -m' mod D-1.

(m' - m)(m' + m) = 0 mod D-1

And the m's would factor D-1, and you subtract 1 for each unique pair {m,m'}.

But there is also the possibility with D-1 a composite that m=0 for multiple cases, so you also subtract for each unique n such that n² = 1 mod D-1, except the trivial cases of n=1 or -1 mod D-1, and in that way can get the full count.

So it is an exercise in combinatorics.

It is possible for the count to be 0, for example that is the case for 12, 16 and 24.

Though 24 is not covered by these relations as D cannot be a perfect square for non-trivial integer solutions to the two conics equation.

The reality that x² - Dy² = 1 steps into the realm of controlling quadratic residues in this way is remarkable and really cool.

So now there is this result that has no mention of what I call the two conics equation, which mathematicians call Pell's Equation, showing it has a power beyond what mathematicians realized and increasingly my research is showing it may be one of the most important control equations in number theory.

So it may be one of the most important number theory equations of them all.


James Harris

Two Conic Diophantine Cycles and Residues

The equation x² - Dy² = 1, which I call the two conics equation was supposedly well-studied by mathematicians but recent research has revealed a wealth of new information, including for the first time in human history the rules for its fundamental solutions, when you have the smallest non-trivial integer solutions.

But there is a lot more. It is a wide-open field. Here I'll consider just a few more things that occurred to me recently, for instance there is a Diophantine cycle associated with the special case of solutions where x = 1 mod D or -1 mod D.

Given x² - Dy² = 1, and x = 1 mod D or x = -1 mod D:

(D-1)j² + (j+1)² = (x+y)², where j = ((x+Dy)-1)/D

or

(D-1)j² + (j-1)² = (x+y)², where j = ((x+Dy)+1)/D

Here's an example with the famous large case D=61:

1766319049² - 61*226153980² = 1

x = 1766319049, y = 226153980, and x = 1766319049 = -1 mod 61, so the second applies.

And (x+Dy+1)/D = 255110030 so the ellipse is:

60*255110030² + 255110029² = 1992473029²

And further research shows j splits into more integers n and m: j = nm or j = 2nm

If x = 1 mod D: (n-m)² - Dm² = 2, or (n-m)² - Dm² = 1

So you cycle into more Diophantine equations. Those equations lead back to two conic equations so you have an infinite cycle, where one is actually the original two conics equation, but written in a different form, which I find amazing.

That was done by the analysis itself, as if it were correcting me.

That alternate form: (n-m)² - Dm² = 1

I've noted previously that leads to a quadratic residue engine:

2m = n^-1(n² - 1) mod D-1

(n - m)² = m² + 1 mod D-1

Here's an example with n=4:

2m = 4^-1(15) mod 21 = 16(15) mod 21, and m = 15

(4 - 15)² = 15² + 1 mod 21

which is: 11² = 16 mod 21

Which shows a forcing of quadratic residue pairs, if m does not equal 0, or if -1 is not a quadratic residue modulo D-1, which remarkably explains their appearance in lists of quadratic residues! They have no choice. These equations force their appearance.

The quadratic residue engine even allows you to count. Since the first is also:

2m = (n - n^-1) mod D-1

That symmetry within means that if D-1 is a prime p, there are approximately (p-1)/2 unique m's, but since half of those m's are just negations of the original, you have a count of roughly (p-1)/4.

One thing that shifts the count is if -1 is a quadratic residue modulo p, then you subtract one more.

So the actual result is that if p is prime and -1 is not a quadratic residue modulo p, it will have (p-1)/4 quadratic pairs, else it will have (p-1)/4 - 1 = (p-5)/4 quadratic pairs. So 2, 3 and 5 do not have any with 7 being the first prime with one.

Those are then exact counts of quadratic pairs for primes. It should be possible to get counts for composites by number of unique prime factors by combinatorics, which is a result I'll leave open.

Intriguingly if D-1 only has as prime factors 2 or 3, m can equal 0 for all n, which can mean no quadratic residue pairs for D-1.

That may offer unique ways to test for primeness for instance if D-1 = 2^c, where c is some arbitrarily large positive integer, then, oh, that goes back to yet another result I haven't covered in this post. Just so much territory.

It's like a wide open space when you open up something of this nature. It's hard to pick and choose among which results to discuss!

Oh, I've become distracted now by Mersenne primes. If D = 2^p, then D-1 may be a Mersenne prime. Ok, off to think some more. Too many possibilities with this thing. May need a few more years.


James Harris

Quadratic Residue Pairs

Remarkably enough the math itself gave me a different way to consider a famous equation, as it gave me a new form when I did some detailed analysis.

It gave me: (n-m)² - Dm² = 1

And that is a seemingly minor shift from the traditional x² - Dy² = 1.

But in my post yesterday I noted that it gives a quadratic residue engine:

2m = n^-1(n² - 1) mod D-1

(n - m)² = m² + 1 mod D-1

Which I just fully realized yesterday and here's a quick example I tossed up.

Let D=12, to see mod 11. And let n=2, then:

2m = 2^-1(3) mod 11 = 6(3) mod 11, so m = 9 mod 11

And now we go to the second equation and have:

(2 - 9)² = 9² + 1 mod 11

which is: 7² = 5 mod 11

With such a new result there is so much to figure out, and already this one is intriguing because it reveals what I've decided to call quadratic residue pairs, which are quadratic residues that differ by 1.

In this case the pair is 4, 5, as both are quadratic residues modulo 11, and they differ by 1.

And it is an awesomely cool result as now you can look at lists of quadratic residues and see some fairly odd things. For instance, if D is a square, so that the original equation does not give integer answers, then you may have no quadratic residues that differ by 1.

Now, if you scan through quadratic residues when D is not a square you'll see there is usually at least one case, except when D-1 is a perfect square. With some exceptions like D=13, where 12 has no quadratic residues that differ by 1.

The behavior is controlled by the second half of the quadratic residue engine:

(n - m)² = m² + 1 mod D-1

There m² plus 1 is forced to be a quadratic residue as well or to equal 0 mod D-1.

But from the first equation of the engine, since n has to be coprime to D-1 for the modular inverse to exist, for m to equal 0 for all n, it must be true that n² - 1 = 0 mod D-1, for all allowed values of n. For D=13, it just so happens that it is. That also happens for D=17, as 16 has no quadratic residues that differ by 1.

And those are things I just figured out while pondering this latest line of approach.

It is beautiful and amazing to me that the math itself gave me a different way to write an equation! And its way is MUCH better than the traditional one, and gives more rules for the behavior of quadratic residues.

The math knew better than people.

It had to show me the better way to write the equation. Wow.

But of course, it makes sense. We are limited by our imaginations while mathematics itself is not.


James Harris

Quadratic Residue Engine

For me it is fascinating continuing to play with x² - Dy² = 1, which has revealed wonderful secrets like the rules governing the fundamental solution, which is what mathematicians call the smallest positive non-trivial integer solution, where the trivial integer solution of course is when y=0.

Mathematicians call x² - Dy² = 1, Pell's Equation, and then usually tell you John Pell doesn't deserve credit, which is weird, but weirder is how little they appear to know about awesome things with regard to it, like in this post I want to show this quadratic residue engine that I finally noticed this morning just a few minutes ago. (Hot, hot research result.)

Turns out that the usual way of displaying it isn't most effective as consider instead:

(n-m)² - Dm² = 1

Just a little change and of course m = y or m = -y from the original, but then n = x+y or n = x-y.

From that format we can now focus on D-1:

n² - 2mn - 1 = (D-1)m²

which is:

n² - 2mn - 1 = 0 mod D-1

So now I can actually solve for m or n to get two equations which are the quadratic residue engine:

2m = n^-1(n² - 1) mod D-1

(n - m)² = m² + 1 mod D-1

And I haven't tried it yet, so here is the moment of truth. Why type up a post before I even do a single numerical example to be sure? I don't know. Seems obvious enough, and if it doesn't work then I just won't put the post up. But enough talking to myself! Let's try a number.

So let D=12, as I want to see mod 11. And let n=2, as that is the first one that will work.

Then:

2m = 2^-1(3) mod 11 = 6(3) mod 11, so m = 9 mod 11

And now we go to the second equation and have:

(2 - 9)² = 9² + 1 mod 11

which is:

7² = 5 mod 11

Which is correct so the equations work and we solved a quadratic residue!

But D-1 prime is boring, as the real question is, what happens if it is a composite? So let's use D=22, so D-1 = 21, and again use n=2:

2m = 2^-1(3) mod 21 = 11(3) mod 21, and m = 6

(2 - 6)² = 6² + 1 mod 21

which is: 4² = 16 mod 21

And that's not remarkable or informative, but let's keep going. Notice that n=3 is blocked because it's not coprime to 21, so the modular inverse doesn't exist. Maybe the math figures we must know it's a factor as something interesting happens at n=4.

2m = 4^-1(15) mod 21 = 16(15) mod 21, and m = 15

(4 - 15)² = 15² + 1 mod 21

which is: 11² = 16 mod 21

Which tells us that 11² = 4² = 16 mod 21, and 11-4 = 7, and 11+4 = 15, which means we can factor 21 with the result.

The math didn't care. It gave either quadratic residue answer.

Of course those are toy examples which I'm doing now as I type up this post. I have no idea if there are any additional constraints that may kick in to limit the efficacy of this result with larger numbers.

But it is remarkable that such a simple little quadratic residue engine was buried in a well-known equation.


James Harris

Under the hood

This post will be primarily mathematical and is to show the building of the factorization I often like to use to show a problem with the ring of algebraic integers, where that ring contradicts what you can prove from the field of complex numbers.

The ring is the ring of objects.

See: http://somemath.blogspot.com/2005/03/object-ring.html

I will be using tautological spaces.

The tautological space is an identity. With it I use what I call a conditional, as unlike the identity, it is not always true.

The conditional is x² + xy + y² = z². It was chosen by me for several reasons but for this discussion the primary importance is that it be in the ring of objects, which it is.

The tautological space is x+y+vz = 0(mod x+y+vz).

x+y = -vz (mod x+y+vz), squaring both sides gives: x² + 2xy + y² = v² z² (mod x+y+vz), subtracting the conditional gives

xy = (v² - 1)z² mod (x+y+vz), so (v² - 1)z² - xy = 0(mod x+y+vz).

From the tautological space itself: x = -y-vz (mod x+y+vz), so I can substitute to get:

(v² - 1)z² + (y+vz)y = 0(mod x+y+vz), so (v² - 1)z² + vzy + y² = 0(mod x+y+vz).

Now let v = -1 + mf, then I have:

(1 - 2mf + m² f² - 1)z² + (-1+mf)zy + y² = 0(mod x+y+vz)

which is:

(m² f² - 2mf )z² + (mf - 1)zy + y² = 0(mod x+y+vz)

Now let P(m) = (m² f² - 2mf )z² + (mf - 1)zy + y².

It's easier to look at it as:

P(m) = y² + (mf - 1)zy + (m² f² - 2mf )z²

My usual example has y = a, m = x, f = 7 and z=1, which is:

P(x) = a² + (7x - 1)a + (7² x² - 2(7)x )

And I've shifted the '7' in front of the variable.

Next I derive the actual factorization. Some of what I do is a bit abstruse, but the point is to make sure everything is being done in the object ring without assumptions.

Now multiply both sides by 4, and complete the square:

4P(m) = 4y² + 4(mf - 1)zy + (mf - 1)² z² - (mf - 1)² z²+ 4(m² f² - 2mf )z²

so:

4P(m) = (2y + (mf - 1)z)² - [ (mf - 1)² - 4(m² f² - 2mf )]z²

Now I need the result that in general x² - y² = (x+y)(x-y), which can be constructed from within the tautological space as an intrinsic property:

x+y+vz = x+y+vz, x= -y - vz + (x+y+vz), squaring both sides, gives:

x² = y² + 2yvz + v² z² - 2(y+vz)(x+y+vz) + (x+y+vz)²

x² - y² = 2yvz + v² z² - 2(y+vz)(x+y+vz) + (x+y+vz)², and setting v = 0, I have:

x² - y² = - 2y(x+y) + (x+y)², which is: x² - y² = (x+y)(-2y + x +y),

so: x² - y² = (x+y)(x-y).

4P(m) = (2y + (mf - 1)z)² + [(mf - 1)² - 4(m² f² - 2mf )]z²

4P(m) = (2y + (mf - 1)z + sqrt[(mf - 1)² - 4(m² f² - 2mf )]z)(2y + (mf - 1)z - sqrt[(mf - 1)² - 4(m² f² - 2mf )]z)

and now I can flip things around so that z is first in each factor and divide the 4 back off:

P(m) = (((mf - 1) + sqrt[(mf - 1)² - 4(m² f² - 2mf )]z/2 + y)(((mf - 1) - sqrt[(mf - 1)² - 4(m² f² - 2mf )]z/2 + y)

and I have a₁(m) = ((mf - 1) + sqrt[(mf - 1)² - 4(m² f² - 2mf )]/2, and

a₂(m) = ((mf - 1) - sqrt[(mf - 1)² - 4(m² f² - 2mf )]/2

where P(m) = (a₁(m)z + y)(a₂(m)z + y).

Note that with y = uf, P(m) has a factor of f.

And that's a complete derivation from conditional all the way through, doing everything in the object ring.

The reason that derivation comes up as an issue is that one objection some people raise is that you can show another contradiction by breaking the construction, for instance with something like:

a² - (x-1)a + (49x² - 14x) = 0

where they just break the original factorization by deleting off a key 7, so that x=1, will zero out the 'a' coefficient.

With what's shown above that's equivalent to just changing:

P(m) = y² + (mf - 1)zy + (m² f² - 2mf )z²

into:

P(m) = y² + (m - 1)zy + (m² f² - 2mf )z²

But that is NOT constructible in the object ring. So it's like just changing something with a derived equation.

This post goes through some of the underlying machinery in order to show a full construction within the object ring, primarily to handle that type of objection.

Also I think it's just way cool.

Figuring out details like the above helped me gain confidence in something I introduced, as I discovered tautological spaces. So I don't have the guide of a lot of history, but had to feel my way mostly on my own.


James Harris

Cool rules, renaming Pell's Equation

For those who'd like the executive summary on what controls fundamental integer solutions to x² - Dy² = 1, here's a short post that just gives them.

Here are the rules for the fundamental solutions to x² - Dy² = 1:

1. If D is prime or twice a prime, solutions will tend to be larger, where the key is those conditions force x = 1 mod D or -1 mod D, and any solution where that is true will tend to be larger.

2. The more small prime factors of D-1, the larger solutions will tend to be.

3. If D is prime or twice a prime, or for any reason x = 1 mod D or -1 mod D, and D-1 has a lot of prime factors, and especially if 4 is a factor then solutions are the largest of all, unless D-1, D+1, D-2, or D+2 is a square, as then solutions will tend to be small regardless, as a sort of release valve kicks in for those special cases.

One cool kind of odd result which really blows up the size is:

If x = 1 mod D, then x+y+(x+Dy-1)/D + 1 must be a square or twice a square.

If x = -1 mod D, then x+y+(x+Dy+1)/D - 1 must be a square or twice a square.

So of course x and y start getting really big as D increases in size to give you that square in there!

An exception though is when D-1, D+1, D-2, or D+2 is a square, as then solutions will tend to be small regardless of other factors.

Those x = 1 mod D or -1 mod D rules follow from a connection to ellipses, and the large impact of that connection can be seen with a famous large case, which is D=61.

1766319049² - 61*226153980² = 1

x = 1766319049, y = 226153980, and x = 1766319049 = -1 mod 61, so the second applies.

The connection to ellipses when x = -1 mod D is

(D-1)j² + (j - 1)² = (x+y)²

with j = (x+Dy+1)/D.

Which gives (x+Dy+1)/D = 255110030.

And it must be true that (x+y +(x+Dy+1)/D - 1) is a square or twice a square:

x+y + (x+Dy+1)/D - 1 = 2247583058, and 2*33523² = 2247583058

60*255110030² + 255110029² = 1992473029²

So, two things come into play to make the solution so large when D=61, as 61 is prime, which forces, x = 1 mod 61 or x = -1 mod 61, and 60 has a lot of small prime factors as 60 = 4*3*5. Both things coming together makes a very large solution which was unknown as the reason before this research.

To see the full derivation of all the rules just read my article Two Conics Equation Size.

If the "mod" is unfamiliar to you, I have an article where I give a quick course on it: Focus on modular arithmetic

Why do mathematicians call it Pell's Equation and then say John Pell doesn't deserve the attribution? I've gotten tired of that error and now call it, the two conics equation.

Such a fun result with an amazing equation! Took me roughly 3 years to figure it all out with a key result posted on my math blog back in 2008. Of course I have been working on other things as well, so it just kind of percolated in the background until I worked it all out.


James Harris

Two Conics Equation Size

A few years ago back in 2008, I decided to use mathematical tools I discovered that I call tautological spaces against binary quadratic Diophantine equations. One of my early results showed how to connect x² - Dy² = 1, which I call the two conics equation, to Pythagorean Triples, and I got that result from a mistake!

Key to my ability to connect the two conics equation to ellipses is a relation that is found by using my method for generally reducing binary quadratic Diophantine equations on the equation:

x² - Dy² = F

That gives:

(x+Dy)² - D(x+y)² = -F(D-1)

With the two conics equation F=1, so I have:

(x+Dy)² - D(x+y)² = -(D-1)

Years ago, when I had an early version of the above I had the variable S, for a piece I didn't know at that time, which is x+Dy. In that post, which I've corrected mathematically, I also am still using the phrase "Pell's Equation" which I did for years before recently shifting to calling it the two conics equation.

Shifting things around a bit, I have:

(x+Dy)² + (D-1) = D(x+y)²

And I can group to divide off D, so doing so and dividing it off:

[(x+Dy)² - 1]/D + 1 = (x+y)²

At this point I made a little mistake years ago, as I wrongly thought that x+Dy = 1 mod D or x+Dy = -1 mod D followed, but that is only definite if D is prime. But it leads to a really cool result, allowing us to connect to ellipses, so now we'll shift to the special case of x = 1 mod D or x = - 1 mod D.

And with that assumption I'll use x+Dy = jD +/- 1, where j is some unknown integer, and one of those cases will be true. That usage is a little confusing, but I did it to keep from having to write x+Dy = jD + 1 or x+Dy = jD - 1, over and over again.

And making that substitution gives:

[(jD +/- 1)² - 1]/D + 1 = (x+y)²

And squaring and simplifying a bit gives:

Dj² +/- 2j + 1 = (x+y)²

So now I just subtract and add j² so that I can complete the square to get:

(D-1)j² + (j +/- 1)² = (x+y)²

And I've successfully connected to ellipses!

Of course if D-1 is a square you are connected to Pythagorean Triples. Here is an example I've used for years.

With D=2, using x=17, y=12, as 17² - 2(12)² = 1, I find:

j = ((17+2*12)-1)/2 = 20 is a solution giving:

20² + 21² = 29²

The +/- usage can be a bit confusing so more recently I've not used it, so the full result without it is:

(D-1)j² + (j + 1)² = (x+y)², j = (x+Dy-1)/D

or

(D-1)j² + (j - 1)² = (x+y)², j = (x+Dy+1)/D

where the first follows if x = 1 mod D, or the second if x = -1 mod D.

Interestingly, of course, that is fulfilled if D is prime, so the result says that ellipses directly connect to the two conics equation, when D is prime.

From that result I did deeper analysis to find out that the prime factors of D-1 control the size of fundamental solutions to x² - Dy² = 1, which is an answer that appears to apply in general, even when x = 1 mod D or x = - 1 mod D is not the case!

So what happened was that in studying my connection I found I got the equation:

(n-m)² - Dm² = 1

So that analysis gave me my main equation back again, but with the variables shifted in this special way, which is kind of cool.

I noticed that I could solve for the residue of m mod D-1, where that split by whether or not D-1 was even, where for the odd D-1:

m = (n² - 1)(2n)^-1 mod (D-1)

While for the even D-1:

m = ((n² - 1)/2)n^-1 mod (D-1)

And I realized that I could have had those results just from considering

(n-m)² - Dm² = 1

without needing the connection to ellipses, or that x = 1 or -1 mod D.

And it is easy to figure out that n = x+y or n = x-y, and the modular inverse requires that n be coprime to D-1, or (D-1)/2 for the even D-1 case, so a lot of small prime factors still provides a harder case, as n is being more and more constrained.

However, if x = 1 mod D or x = -1 mod D is not true, then the impact I think is less, as intriguingly enough if it is true then you also get the requirement that x+y+j+1 or x+y+j-1 must be a square or twice a square.

To see that result only requires a little bit more analysis, where I start with:

(D-1)j² + (j+1)² = (x+y)²

note that:

(j+1)² - (x+y)² = 0 mod D-1

Now consider any prime factor p of D-1, then of course it also follows that:

(j+1)² - (x+y)² = 0 mod p

But now consider j = ((x+Dy)-1)/D, and since D-1 = 0 mod p, I have j = x+y-1 mod p, which remarkably forces all prime factors of D-1 into: (j+1 -(x+y))

Going back to my original full expression:

(D-1)j² + (j+1)² = (x+y)²

that of course is:

(D-1)j² = (x+y - (j+1))(x+y + (j+1))

From x² - Dy² = 1 itself I have x² - y² = 1 mod p, so x+y must be coprime to D-1.

And knowing that D-1 is a factor of (x+y - (j+1)), it must be coprime to (x+y + j+1) for all its primes except 2.

Also then (x+y + j+1) is forced to be a perfect square or twice a perfect square.

Doing the above analysis with

(D-1)j² + (j-1)² = (x+y)²

merely shifts to D-1 a factor of (x+y - (j-1)), and (x+y + j-1) coprime to it for all odd factors.

So when D is a prime, and D-1 has a lot of small prime factors, the mathematics has to fulfill a special requirement, which also connects it to ellipses, which I just mention again as I think it is really cool.

An exception though is when D-1, D+1, D-2, or D+2 is a square, as then solutions will tend to be small regardless of other factors.

There trivially easy solutions to x² - Dy² = 1 exist, which I found by exploring the connection even further, where I found I needed to split j up into two more variables:

j = nm or j = 2nm

The gave me a control set of relations when D-1 is odd, where at least one will work:

1. n = m +/- sqrt(Dm² + 2), m = (n² - 2)(2n)^-1 mod (D-1)

2. n = m +/- sqrt(Dm² + 1), m = (n² - 1)(2n)^-1 mod (D-1)

3. n = m +/- sqrt(Dm² - 2), m = (n² + 2)(2n)^-1 mod (D-1)

4. n = m +/- sqrt(Dm² - 1), m = (n² + 1)(2n)^-1 mod (D-1)

and, when D-1 is even:

1. n = m +/- sqrt(Dm² + 2), m = ((n² - 2)/2)n^-1 mod ((D-1)/2)

2. n = m +/- sqrt(Dm² + 1), m = ((n² - 1)/2)n^-1 mod ((D-1)/2)

3. n = m +/- sqrt(Dm² - 2), m = ((n² + 2)/2)n^-1 mod ((D-1)/2)

4. n = m +/- sqrt(Dm² - 1), m = ((n² + 1)/2)n^-1 mod ((D-1)/2)

You can see the trivial solutions at D-1, a square, when Pell's Equation connects directly to Pythagorean triples, and also at D+1, D-2, and D+2 perfect squares. With those the square root is trivial to resolve with m=1, so it's like a release valve. There are also corresponding identities that give solutions trivially. For instance the D+1 trivial case is given by: n² - (n² - 1)(1)² = 1

In wondering why I made a mistake back in 2008 that was equivalent to assuming that x = 1 mod D or x = -1 mod D, I'm not sure, but might have been in a hurry, or just not thinking carefully. I had just done a lot of the analysis and was anxious to find something useful with my Quadratic Diophantine Theorem. Or in the back of my mind I may have been assuming D was prime. The D=61 case is a famously large case and there of course D is prime.

Then I wandered off and did other things. Only recently have I completely re-visited the result and last night noticed the mistake.

Oh, it is of interest I think to test the additional constraints with the results above for the D=61 case, as it is so famous.

1766319049² - 61*226153980² = 1

x = 1766319049, y = 226153980, and x = 1766319049 = -1 mod 61, so the second equations apply.

(D-1)j² + (j - 1)² = (x+y)², j = (x+Dy+1)/D

Which gives j = 255110030, and it must be true that (x+y + j-1) is a square or twice a square:

(x+y + j-1) = 2247583058, and 2*33523² = 2247583058.

Of course 33523 is coprime to D-1, which is 60, and 33523 = 7*4789, so it looks like the math went to the next smallest prime available which was 7, since 2, 3 and 5 were blocked.

60*255110030² + 255110029² = 1992473029²

Often a mistake can crash an argument but in this case it didn't matter much as it still lead to the correct result that D-1 and its prime factors are key, where the effect is simply much larger if D is prime, or if x = 1 mod D, or x = -1 mod D, which can occur even when it is not. Like when D is twice a prime it is forced as well, so those solutions also are much bigger. Fascinating.

Such a cool story. The connections are amazing. It's like all these equations are like a family, and prime numbers are important to the story too!


James Harris

Was an unsolved problem

When I found the answer to why some fundamental solutions for x² - Dy² = 1, which are the smallest integer solutions with y not equal to 0, were much larger than others, I wasn't sure if it was an unsolved problem before my answer, but now I'm sure it was.

Before I had done a lot of web searches on "Pell's Equation" which is what mathematicians commonly call the equation, even though they also say that John Pell doesn't deserve that credit, and I didn't see the issue raised.

But it occurred to me recently to do the search on: Pell's Equation size

That DID bring up links discussing the question including some attempts at getting an answer, so now I know it was an unsolved problem.

My own solution came from connecting the equation which I like to call the two conics equation rather than Pell's Equation, to ellipses. Oh, I do have a lot of posts that have "Pell's Equation" used as I followed the conventional usage until recently.

So I found the following connection to ellipses, which is valid when x = 1 mod D or x = -1 mod D:

(D-1)j² + (j+1)² = (x+y)², j = ((x+Dy)-1)/D

or

(D-1)j² + (j-1)² = (x+y)², j = ((x+Dy)+1)/D

For instance with D=2, using x=17, y=12, as 17² - 2(12)² = 1, I find the first one works:

j = ((17+2*12)-1)/2 = 20 is a solution giving:

20² + 21² = 29²

Now it is remarkably easy to show why prime factors of D-1 solve the problem of the size of the fundamental solution.

With the first relation

(D-1)j² + (j+1)² = (x+y)²

note that:

(j+1)² - (x+y)² = 0 mod D-1

Now consider any prime factor p of D-1, then of course it also follows that:

(j+1)² - (x+y)² = 0 mod p

But now consider j = ((x+Dy)-1)/D, and since D-1 = 0 mod p, I have j = x+y-1 mod p, which remarkably forces all prime factors of D-1 into: (j+1 -(x+y))

Going back to my original full expression:

(D-1)j² + (j+1)² = (x+y)²

that of course is:

(D-1)j² = (x+y - (j+1))(x+y + (j+1))

From x² - Dy² = 1 itself I have x² - y² = 1 mod p, so x+y must be coprime to D-1.

And knowing that D-1 is a factor of (x+y - (j+1)), it must be coprime to (x+y + j+1) for all its primes except 2.

Also then (x+y + j+1) is forced to be a perfect square or twice a perfect square.

If D-1 is prime, then (x+y + j+1) is only limited to not having that one prime as a factor, which is the easiest situation for the math, so fundamental solutions are at their smallest.

But if D-1 has a lot of small prime factors, then x+y+j+1 is forced to be coprime to each of them, except maybe 2, but even then it cannot have 4 as a factor. So the mathematics must look for solutions with more constraints on what is allowed, and still get a square or twice a square with (x+y + j+1).

Doing the above analysis with

(D-1)j² + (j-1)² = (x+y)²

merely shifts to D-1 a factor of (x+y - (j-1)), and (x+y + j-1) coprime to it for all odd factors.

The result then is that D-1 is the control, and its prime factors are what matters, which then was the previously unknown result. And the validity of that focus applies beyond the special case of x = 1 mod D or x = -1 mod D. And it is really actually cool that connecting to ellipses helps give the answer.

Now consider what you can easily see when the focus is on D-1.

I'll show five solutions where D-1 is prime in a row, and start with D = 24, which means 23, 29, 31, 37 and 41 being the primes, D will be 24, 30, 32, 38 and 42. Here are the solutions:

5² - 24(1)² = 1,

11² - 30(2)² = 1,

17² - 32(3)² = 1,

37² - 38(6)² = 1,

13² - 42(2)² = 1

Notice relatively small solutions. Now see what happens when D-1 is divisible by 4, and has other prime factors. So values for D are close to the previous set, I'll start with 24, which gives me D-1 being 28, 32, 36, 40, 44, which means that D will be 29, 33, 37, 41, 45:

9801² - 29(1820)² = 1,

23² - 33(4)² = 1,

73² - 37(12)² = 1,

2049² - 41(320)² = 1,

161² - 45(24)² = 1

The mathematics is having to work harder now, as it deals with the additional constraints forced by the prime factors of D-1.

Given this information people looking for fundamental solutions to x² - Dy² = 1 can know when to expect very large ones, or when the solutions are more likely to be smaller.

The previously unsolved problem has been resolved.


James Harris

Two conics equation

A remarkable little equation has a fascinating story:

x² - Dy² = 1

In the field of rationals it can be solved as a parametric equation:

x = (D + t²)/(D - t²), y = 2t/(D - t²)

And notice that it gives two of the conic sections, as with D less than 0 it gives ellipses, giving the circle itself with D=-1.

With D greater than 0 it gives hyperbolas.

I have no idea how useful it is for, say, drawing those conic sections and haven't seen much on the subject on the web. But it can be used to draw, and D should be related to eccentricity.

Looking now at integer only solutions, so it is a Diophantine equation, which just means integers only, I'll introduce a simple relation.

Given x² - Dy² = F, it must be true that:

(x+Dy)² - D(x+y)² = -F(D-1)

You can verify the correctness of the second result by multiplying out:

x² + 2Dxy +D²y² - D(x² + 2xy + y²) = -FD + F

and

x² + 2Dxy +D²y² - Dx² - 2Dxy - Dy² = -FD + F

so 2Dxy cancels out, and I can move things around to group like so:

x² - Dy² - Dx² + D²y² + FD = F

and notice I have my original equation negatively mirrored inside which is easier to see like so:

x² - Dy² - D(x² - Dy² - F) = F, so: x² - Dy² = F

So we've verified the relation as valid.

And I can use that relation over and over again to get a series. So now let's use it with our two conics equation, which means F=1, and let's use D=2, so now I can get a series, where here are the first five:

1. x² - 2y² = 1

2. (x+2y)² - 2(x+y)² = -1

3. (3x+4y)² - 2(2x + 3y)² = 1

4. (7x + 10y)² - 2(5x + 7y)² = -1

5. (17x + 24y)² - 2(12x + 17y)² = 1

so you can use the simple case of x=1 and y = 0:

1. 1² = 1

2. (1)² - 2(1)² = -1

3. (3)² - 2(2)² = 1

4. (7)² - 2(5)² = -1

5. (17)² - 2(12)² = 1

and get solutions.

That trick, however, only works to give you answers so easily for D=2.

For the curious I've delved far deeper into its use with the two conics equation, and found I could connect the two conics equation to what are called Pythagorean Triples.

And I used it to help explain why some integer solutions to the two conics equation are much bigger or smaller than others. A clue is the number of prime factors of D-1. If D-1 is prime then solutions tend to be small, but if it has a lot of small prime factors, and especially if 4 is a factor then solutions get much larger.

(Editing to note that subsequent research gave the full picture, while at this point I still just had one key part of it.)

For example a famous case is D=61, where 60 makes it big:

1766319049² - 61(226153980)² = 1

But notice that for D=62, because 61 is prime it is much smaller:

63² - 62(8)² = 1

It is possible to trivially prove that an infinite number of integer solutions for x and y exist, using one more equation.

Given

(n² + 1)² - (n² + 2)n² = 1

multiplying out gives:

n⁴ + 2n² + 1 - n⁴ - 2n² = 1

So it simplifies to 1=1, so it's called an identity. In mathematics an equation is called an identity if it simplifies to a simple equality, like x=x or y=y, or 1=1. Notice then we can just let:

x = n² + 1, y = n, and have a solution if D = n² + 2

For example, if n=3, D = 11, and 10² - 11(3)² = 1.

There are other such identities for the curious, and you can guess at them from the one shown.

What I call here the two conics equation is generally considered by mathematicians with integers only as a Diophantine equation, where "Diophantine" just means, integers only, so then D is usually an integer greater than 1, and mathematicians traditionally call the equation Pell's Equation.

But they also note that the name is a mis-attribution to a guy named John Pell. That is, he shouldn't have the equation named after him based on any contributions which he did, so it was a mistake for that to happen, and usually Euler is blamed for that mistake!

So the puzzle is, why don't mathematicians just quit calling it Pell's Equation if that is a mistake?

For years I've followed their tradition, but their tradition also includes ignoring the rational parametric solution, as they just focus on Diophantine equations, which may be a historical oddity as well.

Turns out that Fermat played with finding integer solutions as a competitive game with others and they thought the parametric equation was too easy for that game, as it made finding answers trivial. Finding integer answers only is harder. Their focus on integers only as a game became locked into a mathematical preference by the math community.

Since that was in the 17th century and near four hundred years ago, it seems to me it makes sense in the 21st century to just let that oddity go, use a more explanatory name, and at least mention the parametric solution. Remarkably mathematicians tend to refuse to even mention the parametric equation, except for the circle case. See: http://mathworld.wolfram.com/Circle.html eqns. 16 & 17

Other disciplines are capable of letting go past mistakes.


James Harris

Focus on modular arithmetic

One of the coolest mathematical areas to me is modular arithmetic and it shows up a LOT in my research, as it is a simplification tool, and a lot of my ideas simplify previously difficult and abstract areas of mathematics. It is critical in that simplification.

Most explanations of modular arithmetic that I've seen focus on what they call clock arithmetic, which is where with the clock things just cycle around. So you can't have 100 o'clock.

100 = 4 mod 12

So you have 4 o'clock, as that's the information you need, so succinctly modular arithmetic is about throwing away information you do not need. And with it you can do some really cool things.

Simple rule: with "mod" what is to the right of the equal sign is less than what is to the right of "mod" which is called the modulus. What is on the left of the equal sign may be greater.

When you consider something with "mod" you are said to be "modulo" a particular value, like with clocks you are modulo 12, or modulo 24, if you're not using am and pm.

Most mathematical texts don't use the regular equals sign with "mod" but instead use "≡" which is just adding one more line and if that doesn't show on your browser, it's just adding one more line beneath the normal equals. I did that for a while but soon got tired of it and just use the normal equals without I think losing anything.

As it is a fundamental branch of mathematics you can do an unlimited number of things with "mod" but usually its focus is with Diophantine equations, which are just situations where the answers are all integers, like -1, 0, 1, 2 or 3. So things like e or pi do not show up. And fractions like 1/2 or 1/3 do not usually show up, though they can be useful in a particular way.

Here's an example of something clever you can do with "mod", as, if you're just bored, you might wonder, if you square an integer and add 2, can it be divisible by 5? With modular arithmetic that is:

Does x² + 2 = 0 mod 5 exist?

You can do a lot of typical algebra with modular arithmetic so that is the same as:

x² = -2 mod 5, and you can add 5, to get rid of the negative, because what remains is less than 5, so you get: x² = 3 mod 5

Important nomenclature issue: With 3 mod 5, 3 is called the residue, as it's what's left over, and often 0 is not considered a residue, but sometimes it may be, depending on the author. In my research 0 is not a residue. So, in my writing, the residue is what is to the left of "mod" as long as it is not zero.

Now we can look at all the positive residues modulo 5: 1, 2, 3, 4

And we can square them all: 1, 4, 9, 16

So we have 1 mod 5, 4 mod 5, 4 mod 5, and 1 mod 5

And you can see that only 1 and 4 are the residues when you square residues modulo 5, and they are called quadratic residues.

And our question is answered as 3 is not in that list! So no, it's not possible to add 2 to a square and have an integer divisible by 5.

Or stated another way, we've proven that the Diophantine equation x² + 2 = 0 mod 5 has no solutions.

By focusing only on the necessary information and throwing everything else away, modular arithmetic allows you to answer questions that otherwise might seem impossible to answer, as you can answer questions over infinity.

You might think that the quadratic residue would always look like a square, but go up just a bit to modulo 7, and notice that 3² = 2 mod 7. So, no, the quadratic residue is not necessarily what is sometimes called a perfect square, which is redundant as you can just call it a square.

Now let's ask the math another question, if you multiply a number by 2 can it equal 3 modulo 5?

That is, does 2x = 3 mod 5 exist?

The answer is, yes. That's because of something called the modular inverse, which is a cool thing that lets you move that 2 from the left hand side to the right hand side:

x = (2^-1)3 mod 5

It may seem complicated but it's just a number that you multiply times 2 to get 1 mod 5, and that number is: 3.

3(2) = 1 mod 5, so 3 is the modular inverse of 2 modulo 5.

So now we have: x = (2^-1)3 mod 5 = (3)3 mod 5 = 4 mod 5.

The modular inverse will always exist as long as it is not a factor or does not contain factors of the modulus. So we could not do the same thing with 2x = 3 mod 10, which does not exist.

Here also is where you can use fractions instead, as you could have said:

x = 3/2 mod 5 = 3(3) mod 5 = 4

However, very important, with modular arithmetic something that looks like a fraction is never really a fraction, but is instead an actual whole number where you may use the form of a fraction simply as an intermediate step.

Sometimes you need to move from "mod" to what is called an explicit equation, and that's easy!

For example x = 4 mod 5 is equivalent to x = 4 + 5k, where k is some non-zero integer, where usually you have no idea what its actual value is. That is the information that is being thrown away, so there are an infinity of k's usually that will work. And that goes again to the power of "mod" as it always to some extent involves infinity.

And that is just a quick overview of some of the basics with modular arithmetic, where you can learn a lot more as it is a huge subject from many sources including the Wikipedia article on modular arithmetic.


James Harris

Reducing binary quadratic Diophantines

As much as I talk about other key discoveries, I have talked less about my results about binary quadratic Diophantine equations, though a key one allows a one-step way to generally reduce binary quadratic Diophantine equations.

Given an equation of the form

c₁x² + c₂xy + c₃y² = c₄ + c₅x + c₆y

I've proven that you can reduce to

(A(x+y) - B)² - As² = B² - AC

which is itself a binary quadratic with (x+y) and s unknowns, where

A = (c₂ - 2c₁)² + 4c₁(c₂ - c₁ - c₃)

B = (c₂ - 2c₁)(c₆ - c₅) + 2c₅(c₂ - c₁ - c₃)

and

C = (c₆ - c₅)² - 4c₄(c₂ - c₁ - c₃)

when neither A nor B equals 0.

As a first example let c₁ = 1, c₂ = 1, c₃ = 1, c₄ = 1, c₅ = 1, c₆ = 1, so:

x² + xy + y² = 1 + x + y

Which gives:

A = -3, B = -2, and C = 4

So the equation reduces to:

(-3(x+y) + 2)² + 3s² = 16

which works with s=0. So -3(x+y) + 2 = 4 or -4 should work, and the latter gives x+y=2, and you can substitute out x or y in the original equation to solve that way, where x=y=1 is a solution.

For a second example let c₁ = 1, c₂ = 2, c₃ = 3, c₄ = 4, c₅ = 5, c₆ = 6, so:

x² + 2xy + 3y² = 4 + 5x + 6y

Which gives:

A = -8, B = -20, and C = 33

And substituting and dividing 4 from both sides the equation reduces to:

(-4(x+y) + 10)² + 2s² = 166

which is:

(-4(x+y) + 10)² = 166 - 2s² = 2(83 - s²)

Running through possible odd s's I notice that s=9 works to give -4(x+y) + 10 = 2 or -2, so x+y = 2, or x+y = 3. And x = 4, y = -2, or x = 5, y = -2 work.

The reducing form involves a completion of the square, as notice you can just multiply it out and also use the form:

A(x+y)² - 2B(x+y) + C = s²

Note that form is necessary if A or B equals 0, because then you can't complete the square to get the other form.

This approach will work for any binary quadratic Diophantine equation except for if:

c₂ - 2c₁ = c₂ - c₁ - c₃ = c₆ - c₅ = 0

However that special case is easily handled, for example:

x² + 2xy + y² = c₄ + x + y

is: (x+y)² - (x+y) - c₄ = 0

And that form is equivalent to a unary case anyway, which is probably why my equations won't handle it. I worked out exactly why years ago, but don't remember enough to say that for certain.

I look at those equation every once in a while, just kind of wondering.

My method is to my knowledge the only known that turns reducing any binary quadratic Diophantine, except the special case as noted, into a one-step process.


James Harris