Translate

Friday, October 21, 2011

Two Conics Equation Solutions

Solving for modular solutions to x2 - Dy2 = 1, is surprisingly easy, with an alternate form. Consider

(z-y)2 - Dy2 = 1

as then z2 - 2zy + y2 - Dy2 = 1, so I can group to find D-1 makes an appearance:

z2 - 2zy - (D-1)y2 = 1, so z2 - 2zy - 1 = (D-1)y2

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

2y = z-1(z2 - 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 x2 - Dy2 = 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)2 - Dy2 = 1

Then we solve to find:

2y = (kz)-1(z2 - 1) mod D-k2

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 k2, 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

Wednesday, October 19, 2011

Two Conics Equation Modular Solutions

It is weird to try and absorb just how much was missed with x2 - Dy2 = 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)2 - Dm2 = 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:

n2 - 2mn - 1 = (D-1)m2

which is:

n2 - 2mn - 1 = 0 mod D-1

And I can just solve for m: 2m = n-1(n2 - 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 x2 - Dy2 = 1 that:

2y = n-1(n2 - 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(62 - 1) mod 37 = 31*(36-1) mod 37 = 12 mod 37

So I get y = 6 mod 37, and with this picked example 372 - 38(6)2 = 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 x2 - Dy2 = 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)2 - Dm2 = -1

n2 - 2mn + 1 = (D-1)m2

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

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

So easily enough for (n-m)2 - Dm2 = 2, I have: 2m = n-1(n2 - 2) mod D-1

And finally, for (n-m)2 - Dm2 = -2, I have: 2m = n-1(n2 + 2) mod D-1

Those alternate forms if they have solutions actually lead to solutions for the original x2 - Dy2 = 1, but they may not have solutions. For instance each requires a quadratic residue, for instance (n-m)2 - Dm2 = -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)2 - Dm2 = -1

2m = n-1(n2 + 1) mod D-1, (n - m)2 = m2 - 1 mod D-1


2. (n-m)2 - Dm2 = 2

2m = n-1(n2 - 2) mod D-1, (n - m)2 = m2 + 2 mod D-1


3. (n-m)2 - Dm2 = -2

2m = n-1(n2 + 2) mod D-1, (n - m)2 = m2 - 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 x2 - Dy2 = 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

Tuesday, October 11, 2011

Counting quadratic residue pairs

The story of x2 - Dy2 = 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)2 - Dm2 = 1.

The quadratic residue engine is simple enough:

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

(n - m)2 = m2 + 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 x2 - Dy2 = 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(n2 - 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(n2 - 1) = n'-1(n'2 - 1) mod D-1

Then:

n'*n2 - n' = n*n'2 - n mod D-1, so

n'*n2 - n*n'2 = 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(n2 - 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 m2 = -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)2 = m2 + 1 mod D-1

Then of course m'2 = m2 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 n2 = 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 x2 - Dy2 = 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

Saturday, October 08, 2011

Two Conic Diophantine Cycles and Residues

The equation x2 - Dy2 = 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 x2 - Dy2 = 1, and x = 1 mod D or x = -1 mod D:

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

or

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

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

17663190492 - 61*2261539802 = 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*2551100302 + 2551100292 = 19924730292

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

If x = 1 mod D: (n-m)2 - Dm2 = 2, or (n-m)2 - Dm2 = 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)2 - Dm2 = 1

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

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

(n - m)2 = m2 + 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)2 = 152 + 1 mod 21

which is: 112 = 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 = 2c, 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 = 2p, 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

Wednesday, October 05, 2011

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)2 - Dm2 = 1

And that is a seemingly minor shift from the traditional x2 - Dy2 = 1.

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

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

(n - m)2 = m2 + 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)2 = 92 + 1 mod 11

which is: 72 = 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)2 = m2 + 1 mod D-1

There m2 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 n2 - 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

Tuesday, October 04, 2011

Quadratic Residue Engine

For me it is fascinating continuing to play with x2 - Dy2 = 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 x2 - Dy2 = 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)2 - Dm2 = 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:

n2 - 2mn - 1 = (D-1)m2

which is:

n2 - 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(n2 - 1) mod D-1

(n - m)2 = m2 + 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)2 = 92 + 1 mod 11

which is:

72 = 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)2 = 62 + 1 mod 21

which is: 42 = 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)2 = 152 + 1 mod 21

which is: 112 = 16 mod 21

Which tells us that 112 = 42 = 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