Translate

Wednesday, December 04, 2013

Binary Quadratic Modular Constraints

Abstract: Basic facts of modular arithmetic and elementary methods lead in general to an infinite set of modularly independent constraining modular equations for binary quadratic Diophantine equations.

The fundamental equation for binary quadratic Diophantine equations is x2 - Dy2 = F, as it can be shown that such equations are in general reducible to this basic quadratic form.

From that form one can use basic facts of modular arithmetic to get solutions for x and y modulo N, if D is a quadratic residue modulo N.

x2 - Dy2 = F = (x - my)(x + my) mod N

Where: m2 = D mod N follows trivially with r any residue modulo N for which F/r mod N exists:

2x = r + F/r mod N and 2my = r - F/r mod N

However, the basic principle that quadratic residues offer a potential modular factorization, can also be used to again solve for x and y, where instead F is the quadratic residue.

x2 - F = Dy2  = (x - m')(x + m') mod N'

Where now: m'2 = F mod N'

And that gives me solutions:

2x = r + (Dy2)/r mod N' and 2m' = r - (Dy2)/r mod N'

Which means:

y2 = (r2 - 2m'r)/D mod N'

Where here r is some residue modulo N' for which y exists.

So here y can be found modulo N', where you have two solutions, if they exist, from the quadratic residue, while x will continue to have only one solution for each.

Notice that these equations are modularly independent as N does not necessarily equal N'. And there are an infinite number of cases available where N does not equal N'.

That independence cuts into the potential infinity of solutions available for x and y modularly, meaning that you can cross check between them if you have a prime p shared between N and N', with the possibility of fewer solutions.

Conceivably you may actually find that values for x and y are given that only exist for the explicit x and y, which will of course always be available solutions, if they exist.

However, there are more potentially constraining equations available from a key result of mine.

I discovered that if you have

u2 + Dv2 = F

then it must be true that

(u-Dv)2 + D(u+v)2 = F(D+1)

(Note while the result is derived, confirmation of it is trivial as you can simply multiply out, simplify, and see that the second equations reduces back to the first.)

That is an iteration that can be continued, and switching back to the basic equation I have been using up until this point and giving the first four iterations I have:

1. x2 - Dy2 = F

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

3. ((1+D)x+2Dy)2 - D(2x + (1+D)y)2 = F(-D+1)2

4. ((1+3D)x + (D2 + 3D)y)2 - D((3+D)x + (1+3D)y)2 = F(-D+1)3

5. ((D2 + 6D + 1)x + (4D2 + 4D)y)2 - D((4+4D)x + (D2 + 6D + 1)y)2 = F(-D+1)4

And you can keep going forever.

Notice that our prior approach works with any iteration. For example, consider 3., where we then have:

m2 = D mod N

With r, any residue modulo N for which F(-D+1)2/r mod N exists then:

2x = r +  F(-D+1)2/r mod N and 2my = r -  F(-D+1)2/r mod N

And for our second set of constraints, again using 3., we have:

Where now: m'2 = F(-D+1)2 mod N'

But that gives me solutions:

2((1+D)x+2Dy) = r + (D(2x + (1+D)y)2)/r mod N' and

2m' = r - (D(2x + (1+D)y)2 )/r mod N'.

Which means:

(2x + (1+D)y)2  = (r2 - 2m'r)/D mod N'

Now you get a solution with a quadratic residue for a congruence with x and y, but you have another such equation from the first, so can still solve for x and y modulo N' trivially, if a solution exists!

So how applicable is this result in general?

It can be shown that you are lead to an infinity of results for all binary quadratic forms, except for:

x2 - y2 = 1

In that case both D = 1, and F = 1, which zeroes out the iterative possibilities. However that trivial unary case would not limit potential efficacy of this approach, but should be noted.

Therefore, it is proven that there exists an infinity of modular constraining equations for binary quadratic Diophantine equations except for the unary case as noted.

Practical considerations are outside of the scope of this paper, which is focused on settling theoretical aspects.


James Harris