Harristotelian Logic

Given a target composite T and integer factors f_1 and f_2, such that f_1*f_2 = T, and any prime p, the following relations must be true:

f_1 = ak mod p

and

f_2 = a^{-1}(1 + a^2)k mod p

where

k^2 = (a^2+1)^{-1}(T) mod p.

Example: T=119, p=11, and a=2 gives k^2 = (5)^{-1}(119) mod 11 = 9(9) mod 11 = 4 mod 11.

And k = 2 mod 11 is a solution, so f_1 = 4 mod 11, and f_2 = 2^{-1} (1+4)(2) mod 11 = 5 mod 11.

In this case, subtracting 11 gives one prime factor as f_1 = -7 mod 11, and f_2 = -6 mod 11. Subtracting 11 again from f_2 gives -17.

If you want positive solutions, look for other a's that work and see what happens.

You can test those congruences with any factorization you like. They are derived and follow from mathematical proof.

I had been giving z mod p and y mod p and saying you should look at z-y mod p and z+y mod p.

The difference here is I just give them for you.