Tuesday, March 24, 2009

Dual factorizations with Pell's Equation

In rationals starting with Pell's equation:

x2 - Dy2 = 1

I have proven that

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

where j = ((x+Dy) -/+1)/D.

Here the +/- indicates that one variation will work so it is an OR and not an AND. Either plus OR minus will give a valid j.

It suffices to substitute out j, and simplify, which will give Pell's Equation again, showing the relations are valid.

Dual factorizations:

(x-1)(x+1) = Dy2

gives an opportunity to factor D, which I will declare to be an odd composite.


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

gives the opportunity factor D-1.

Focusing on the second factorization, note to generalize I need additional variables.

Introducing u and v, where j = uv, I further need factors f1 and f2 where f1f2 = D-1.

Then I have for generality

(x+y - (uv+/-1)) = uf1


(x+y + (uv+/-1)) = uv2f2

Note that f1 and f2 can be declared to be integers, and further that x and y uniquely determine u and v, as consider:

(x+y + (uv+/-1)) = (uv)vf2

where I remind that j = ((x+Dy) -/+1)/D = uv, so given any x and y in rationals, I can simply separate off all non-unit non-zero integer factors in common with D-1, for f1 in the first, and for f2 in the second, leaving u and v as rationals, and trivially solved and proven to exist as rationals.

Therefore, it is proven that for every x and y that fulfill Pell's Equation there is a u and v pair.

Given that there must exist x and y, such that (x-1)(x+1) = Dy2, non-trivially factors D, it is proven there exists a u and v pair unique to any such cases.

That completes the underlying mathematical proof showing the dual factorization and proving the existence of rational v, for a non-trivial factorization of a composite D.

It is now possible to move further into the utility of these expressions and reveal a direct factoring method.

There are then three equations available:

(x+y - (uv+/-1) = uf1

(x+y + (uv+/-1) = uv2f2

((x+Dy) -/+1)/D = uv

Considering x and y to be unknowns it follows then that x and y can be determined as functions of v. Doing so gives:

y = 2[f2v - 1]/[D - (f2v - 1)2]


x = [D + (f2v - 1)2]/[D - (f2v - 1)2]

where v must be nonzero.

But then for a non-trivial factorization, f2v - 1 must have that non-trivial factor as its factor.

If you consider x as a ratio of integers r and t, where x = r/t, for a non-trivial factorization of D, an odd composite, where D = g1g2 where the g's are integers, then a solution for x must exist with:

r = (g1 + g2)/2, and t = (g1 - g2)/2.

However, adding the numerator and denominator of x above gives 2D, meaning that they are not coprime, and one of the factors must be a non-trivial factor of D.

If that factor is g2, then a boundary condition is:

g2(g1 + g2) < 2D

so, g22 < sqrt(D), must be true, for that case, meaning D cannot be a square.

Now then, if f2v - 1 = g2, then

v < (sqrt(D) - 1)/f2

is a boundary condition.

That allows you to get search conditions for v, but it's not clear at this time if there is any significant benefit to using this approach.

I will note that if f2 - 1 <= g2, then there must be an integer v satisfying the condition which will non-trivially factor with f2. The bottom default case is f2 = 2, or 1, which of course, has the highest number of possible searches, so if there is a connection available it would be preferable with the largest f2 possible.

I had hopes that this approach solved the factoring problem, but had failed to simplify my equations sufficiently to see that the shared factor in common with D between the numerator and denominator of x, precluded the simple solution I thought was available.

James Harris

No comments: