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 – c1 and q = s + c2 for some nonnegative integers c1 and c2.
s + c2 = m / (s – c1) = (s2 – r)/(s – c1) = s + (c1s – r)/(s – c1), and so,
c2 = (c1s – r)/(s – c1), and so the search is for a value of c1 that makes the quotient divide evenly: a value for which s – c1 divides c1s – r.
The numerator is 0 times the denominator at c1 = r/s, which will never be an integer. The numerator is n times the denominator, or, equivalently, c2 = n at:
c1s – r = ns – nc1, or c1 = (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 c1 that will also give c2, 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