Harristotelian Logic

The following post steps through the mathematical underpinnings of a remarkably simple factoring method which relies on dual factorizations. It steps off from the familiar Pell's Equation—with rationals—and through basic algebra proves a viable factoring technique.

In rationals starting with Pell's equation:

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:

The utility of the expressions comes from 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)) = u*f_1

and

(x+y + (uv+/-1)) = u*v^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)*v*f_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 utilities of these expressions and reveal a direct factoring method.

There are then three equation available:

(x+y - (uv+/-1) = u*f_1

(x+y + (uv+/-1) = u*v^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 = [+/-2Dv/(f_1 - f_2*v^2 - 2v) +/- 1 -/+(f_1 + f_2*v^2)/(f_1 - f_2*v^2 - 2v)]/(D-1)

and

x = +/-(f_1 + f_2*v^2)/(f_1 - f_2*v^2 - 2v) - [+/-2Dv/(f_1 - f_2*v^2 - 2v) +/- 1 -/+(f_1 + f_2*v^2)/(f_1 - f_2*v^2 - 2v)]/(D-1)

Given that y and x are now expressed as functions of v, f_1 and f_2, it is now possible to elucidate a fairly simple factoring method. Said method requires the addition of new functions, so let x = r(v)/t(v), and y = s(v)/t(v), where r(v) is the numerator of the x function, s(v) is the numerator of the y function, and t(v) is the denominator.

Note that t(v) is the easiest given as:

t(v) = f_1 - f_2*v^2 - 2v

Then making the substitutions into the factorization of Pell's Equation: (x-1)(x+1)=Dy^2, and simplifying slightly, I now have

(r(v) - t(v))(r(v) + t(v)) = D(s(v))^2

Note that it suffices if r(v) and t(v) are integers for

abs(r(v) - t(v)) < D and abs(r(v) + t(v)) < D

to guarantee a non-trivial factorization. The absolute values may at first seem problematic, but note that if D is positive then the right side must be positive, forcing the two expressions to match by sign. So it is possible to simply add them, giving the result:

abs(2r(v)) < D

So remarkably, it is proven that rational v must be found such that r (v) is an integer and abs(r(v)) < D/2, and you are guaranteed to non-trivially factor D.

That completes the proof. The factoring problem is then, solved.

Comments or questions are appreciated.

Thank you for your time and attention.