Consider the positive integer m which is the product of distinct primes p and q. Consider s, the smallest integer greater than the square root of m, and the difference r = s^2 – m.

p will be less than s, and q will be greater than s. Thus p = s – c_{1} and q = s + c_{2} for some nonnegative integers c_{1} and c_{2}.

s + c_{2} = m / (s – c_{1}) = (s^{2} – r)/(s – c_{1}) = s + (c_{1}s – r)/(s – c_{1}), and so,

c_{2} = (c_{1}s – r)/(s – c_{1}), and so the search is for a value of c_{1} that makes the quotient divide evenly: a value for which s – c_{1} divides c_{1}s – r.

The numerator is 0 times the denominator at c_{1} = r/s, which will never be an integer. The numerator is n times the denominator, or, equivalently, c_{2} = n at:

c_{1}s – r = ns – nc_{1}, or c_{1} = (ns+r)/(s+n). This is somewhat similar to the equation of the divisibility statement above. When I put it on the program code, it produced prime factor q rather than p.

So the search for c_{1} that will also give c_{2}, from which will follow the values of p and q that factor m, is equivalent to the search for a value of n greater than 1 so that s+n evenly divides ns+r.

Is this a significant result? That depends on how easily one can determine the integer points at which the values of linear equations with integer coefficients evenly divide one another. It is possible that the ease is no greater than that of trial division for finding p and therefore q. But I am not sure.

## Leave a ReplyCancel reply