Thursday, September 27, 2007
Puzzling over latest surrogate factoring
Recently I started considering a reverse approach with what I call surrogate factoring and have been puzzling over it. It seems that there are factorizations with small test numbers that indicate some mathematical requirement but I haven't been able to prove it!
In any event, here's the approach I am puzzling over.
With a target composite S, where
(x+k)^2 = y^2 + S
consider a non-trivial factorization, x+k-y = f_1 and x+k+y = f_2, where S = f_1*f_2, so k is some chosen non-zero integer, so x and y are then determined by the factorization.
Now expanding gives
x^2 + 2xk + k^2 = y^2 + S
and if you assume ahead of time some non-zero integer T, such that x^2 = y^2 + n_1*T, then
2xk + k^2 = S + n_1*T
and if you subtract 2k^2 from both sides then you have
2xk - k^2 = S - 2k^2 + n_1*T
and NOW if you assume that S - 2k^2 = n_2*T, you have
2xk - k^2 = (n_2 + n_1)* T, so
n_1 + n_2 = (2xk - k^2)/T
where now you have that T needs to be a factor of 2xk - k^2, and if you look at factors coprime to k, the real focus is on 2x - k, and I've checked with some test factorizations and it always has been such that n_1 and n_2 are integers.
If that were a rigid requirement then there would always exist some T a factor of S - 2k^2, such that
x = (k+T)/2 if k is odd, or
x = k/2 + T
if k is even, assuming that S is odd, as why have an even S to factor.
The weird thing to me is that it has worked with dinky test numbers and I don't know why, as couldn't it be true that no prime factors were in common between S - 2k^2, x^2 - y^2, and 2x - k, given
x+k-y = f_1 and x+k+y = f_2
where S = f_1*f_2?
After all, k is then the only choice as x and y are then forced by a non-trivial factorization, for instance,
2(x+k) = f_1 + f_2.
Oh, there is one remarkable thing as well in that trivial factorizations are blocked!!!
It's not possible for this technique to pull S itself as f_1 or f_2, where there is an easy little proof of that fact.
In any event, here's the approach I am puzzling over.
With a target composite S, where
(x+k)^2 = y^2 + S
consider a non-trivial factorization, x+k-y = f_1 and x+k+y = f_2, where S = f_1*f_2, so k is some chosen non-zero integer, so x and y are then determined by the factorization.
Now expanding gives
x^2 + 2xk + k^2 = y^2 + S
and if you assume ahead of time some non-zero integer T, such that x^2 = y^2 + n_1*T, then
2xk + k^2 = S + n_1*T
and if you subtract 2k^2 from both sides then you have
2xk - k^2 = S - 2k^2 + n_1*T
and NOW if you assume that S - 2k^2 = n_2*T, you have
2xk - k^2 = (n_2 + n_1)* T, so
n_1 + n_2 = (2xk - k^2)/T
where now you have that T needs to be a factor of 2xk - k^2, and if you look at factors coprime to k, the real focus is on 2x - k, and I've checked with some test factorizations and it always has been such that n_1 and n_2 are integers.
If that were a rigid requirement then there would always exist some T a factor of S - 2k^2, such that
x = (k+T)/2 if k is odd, or
x = k/2 + T
if k is even, assuming that S is odd, as why have an even S to factor.
The weird thing to me is that it has worked with dinky test numbers and I don't know why, as couldn't it be true that no prime factors were in common between S - 2k^2, x^2 - y^2, and 2x - k, given
x+k-y = f_1 and x+k+y = f_2
where S = f_1*f_2?
After all, k is then the only choice as x and y are then forced by a non-trivial factorization, for instance,
2(x+k) = f_1 + f_2.
Oh, there is one remarkable thing as well in that trivial factorizations are blocked!!!
It's not possible for this technique to pull S itself as f_1 or f_2, where there is an easy little proof of that fact.