Even if I'm not sure it works, it's worth it for me to put forward the ideas for what might be a general solution algorithm for binary quadratic Diophantine equations just in case it does work.
Coming up with a general solution algorithm would complete my research in this area, as I already have a general method for reducing. For me the idea of a complete theory is enticing.
A complete theory of binary quadratic Diophantine equations would be a boon to research.
The reduced form for binary quadratic Diophantine equations x2 - Dy2 = F can be easily solved modularly to give:
y2 = (x2 - F)/D mod N
where x is some residue modulo N. If x and y have explicit solutions there must be some x mod N, for which (x2 - F)/D will be a quadratic residue. And it is possible to probe more deeply with a slightly more complex solution to get more information about what is happening internally, and also reveal an additional constraint.
It can be shown that x2 - Dy2 = F can also be solved modularly to give:
y2 = (r2 - 2mr)/D mod N, x = r + (Dy2)/(2r) mod N
Where N can be any integer for which F is a quadratic residue, where: m2 = F mod N, and r is a residue modulo N, for which y exists.
This result is found by the modular factorization:
x2 - F = Dy2 = (x - m)(x + m) mod N
by considering r, a residue of N, where: x+m = r, and x-m = (Dy2)/r
Proof:
Given x2 - Dy2 = F, consider N such that F is a quadratic residue modulo N, so there must exist m such that m2 = F mod N.
Then we have trivially: x2 - F = x2 - m2 = (x - m)(x + m) mod N
Now consider r modulo N, such that:
x2 - F = r[(Dy2)/r] = (x + m)(x - m) mod N
The existence of r is a result of F being a quadratic residue of N, as only then must there exist at least two residues modulo N that give Dy2 mod N as their product, if solutions exist.
Let: x+m = r mod N, and x-m = (Dy2)/r mod N
Solving gives:
2x = r + (Dy2)/r mod N and 2m = r - (Dy2)/r mod N
And using the second I can solve for y2:
y2 = (r2 - 2mr)/D mod N
So I have finally:
y2 = (r2 - 2mr)/D mod N, x = r + (Dy2)/(2r) mod N
Proof complete.
Notice that r = 2m mod N, will always give x = m mod N and y = 0 mod N, so it is not giving unique information, which is also true for r = -2m mod N. However, if explicit solutions do exist and there are no other solutions it means y = 0 mod N. If it's not already known that explicit solutions must exist, no other solutions except the default one may mean no explicit solutions exist.
This result shows that N being made up of primes for which F is a quadratic residue is mathematically significant, as it increases the complexity, with the existence of r.
The existence of r and the requirement that (r2 - 2mr)/D be a quadratic residue of N gives constraints which may highlight explicit solutions because they have a 100% probability of giving an r, if they exist, which suggests a rather basic modular solution algorithm.
Modular algorithm:
Collect a list of primes p for which F is a quadratic residue. That should be the case for at least 50% of primes or for all primes if F is a square. The needed size of that list will depend on the size of x and y necessary to factor. The primorial gives roughly the size of solution that can be handled by any particular number of primes in the list.
Given two primes p1 and p2 on that list, Let N equal the product of the two primes, and calculate y and x, which may have multiple solutions. There will be two values for m and you need to use both! While there may be two distinct solutions for y for any particular r that works, as you're solving a quadratic residue to get it, you only need one, as modulo each prime they only vary by sign.
Discard values where r = 2m or -2m mod N, as those always exist and give no useful information, unless you know there must exist explicit solutions and no other values give solutions. In that case then you know y = 0 mod N is forced. For other cases where y2 = 0 mod N verify that calculated x and y = 0 mod N actually work with x2 - Dy2 = F mod N. Discard any cases where they do not.
Solutions can vary only by sign, where you need a consistent way of handling sign variations.
For example: 5 mod 10 and 10 mod 5 only vary by sign as 10 mod 5 is -5 mod 15. You don't necessarily want to look at those as different solutions since both x and y are squared in the root equation. You might always just take the smaller, so check to see if you have a negation.
There must be solutions if the explicit equation has solutions. If you find no solutions, except the default case, for any prime p for which F is a quadratic residue then there may be no solutions to the explicit equation. But you don't know for sure with just a single case.
Save possible x and y modular values, increment the count for a solution residue by prime.
For example, with N = p1p2, you have x mod p1p2, but would save x mod p1 and x mod p2, so you save by prime.
Save linked prime and its residue for a particular prime if the other prime is the next smallest prime, assuming your list goes from smallest prime to greatest. That way each prime is linked to only one other.
Repeat with each combination of your list of primes by 2, and keep a hit count for each factor modulo a particular prime.
After you have completed looping through all prime combinations by two, and stored values by prime, incrementing the counts of particular residues by prime as they are verified, you should have resonance spikes around values that come from the explicit solutions.
That is, the values with the highest counts should be values from the explicit solutions.
If there are no spikes then you have a growing probability that no explicit solution exists. As the alternative is that every explicit solution for y has each of your primes as a factor.
If you do have resonance spikes, solve for the explicit x and y using the solutions at each prime, which is of course easy, as for instance you could use the Chinese Remainder Theorem. If you have multiple factors you can use linked primes to tell which go with each other.
I'll use a small example to show some numbers without demonstrating the full algorithm as described above.
Let D = 4, F = -119. I need it negative as I need F mod 4 = 1 for an explicit solution. I note that 3 and 5 are primes that will work, so will take them as a pair with N = 15.
As m2 = F mod N = -119 mod 15 = 1 mod 15, m = 1 mod 15 is a solution. And m = 11 mod 15 is another. Will first use m = 1 mod 15.
So: y2 = 4(r2 - 2r) mod 15
And: x = r + (4y2)/(2r) mod 15
The quadratic residues of 15 are: 1, 4, 6, 9, 10
We find that r = 2, gives 0, and works, but no other values work except:
r = 6 and r = 11, where both give y2 = 6 mod 15, which has y = 6 mod 15 as a solution, and is a non-trivial case.
Solving for x with the first: 2x = 6 + (4(6))/6 mod 15 = 6+4 mod 15 = 10 mod 15, so x = 5 mod 15.
With the second you get 2x = 11 + (4(6))/11 mod 15 = 11 + 9 = 20 mod 15, so x = 10 mod 15, which is of course -5 mod 15.
And x = 5 mod 15 and y = 6 mod 15 work.
And x = 5, and y = 6 work explicitly, which is why it's a small example for basic demonstration purposes.
Now using m = 11 mod 15.
So: y2 = 4(r2 - 22r) mod 15 = = 4(r2 - 7r) mod 15
And: x = r + (4y2)/(2r) mod 15
And r = 7 works, to give x = 11 mod 15 and y = 0 mod 15. That gives 11(11) = 121 which is larger than 119, so beyond interest here.
So why might this thing work where other modular approaches have failed?
Well that limiting quadratic residues is a BIG DEAL.
There is a 100% certainty of a quadratic residue for an r for an explicit solution, but for others the likelihood should be less! Which means you can simply look at counts by r, with resonance spikes around the explicit solutions.
That I could bring in the concept of resonance was really exciting.
Actually running the algorithm could look like watching a spectrometer as peaks built around the explicit solutions while other values had lesser heights. Kind of wonder what it would look like exactly. Would there be lesser mounds or just sharp spikes surrounded by a few odd counts randomly distributed? If it works...
So why really? Well now with x + m = r and x - m = (Dy2)/r, you're balancing the variable x against the constant m, which is the kind of thing that has come up in my research before, so it was eery here to see it valuable again. That gives very little wiggle room. The math has to figure out all kinds of things to make it work! Which means it's hard for me to comprehend the complexity. But it means some values for r are not available, as both x+m and x-m can't behave as needed.
Of course if it DOES resolve by prime then building the full factor is easy. There are a couple of techniques including the Chinese Remainder Theorem, but I like one I found on my own and then discovered was not new.
For instance 7 = 1 mod 3 and and 7 = 2 mod 5.
Using the formula gives it right back: 1 + 3(2) mod 15 = 7 mod 15
So 1 mod 3 and 2 mod 5 give you 7.
The ability to describe a number with its residues by prime is kind of cool. So yeah, if you have the prime residues then you have the number, where you need fewer primes than the closest value of the primorial to your number. And the primorial rises faster than the factorial!
James Harris
No comments:
Post a Comment