x

^{2}- Dy

^{2}= 1

I have proven that

(D-1)j

^{2}+ (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) = Dy

^{2}

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

While

(D-1)j

^{2}= (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 f

_{1}and f

_{2}where f

_{1}f

_{2}= D-1.

Then I have for generality

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

_{1}

and

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

^{2}f

_{2}

Note that f

_{1}and f

_{2}can be declared to be integers, and further that x and y uniquely determine u and v, as consider:

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

_{2}

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 f

_{1}in the first, and for f

_{2}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) = Dy

^{2}, 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) = uf

_{1}

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

^{2}f

_{2}

((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[f

_{2}v - 1]/[D - (f

_{2}v - 1)

^{2}]

and

x = [D + (f

_{2}v - 1)

^{2}]/[D - (f

_{2}v - 1)

^{2}]

where v must be nonzero.

But then for a non-trivial factorization, f

_{2}v - 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 = g

_{1}g

_{2}where the g's are integers, then a solution for x must exist with:

r = (g

_{1}+ g

_{2})/2, and t = (g

_{1}- g

_{2})/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 g

_{2}, then a boundary condition is:

g

_{2}(g

_{1}+ g

_{2}) < 2D

so, g

_{2}

^{2}< sqrt(D), must be true, for that case, meaning D cannot be a square.

Now then, if f

_{2}v - 1 = g

_{2}, then

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

_{2}

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 f

_{2}- 1 <= g

_{2}, then there must be an integer v satisfying the condition which will non-trivially factor with f

_{2}. The bottom default case is f

_{2}= 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 f

_{2}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:

Post a Comment