## Integer Factorization: Recap, October 17, 2023

It is time for a review of what I have found in my study, in order for me to figure out where to head next.

INTRODUCTORY CONCEPTS AND REMARKS

Let m be an odd positive integer.

When m = ab for a and b also odd positive integers, this gives a factorization of m.

It is always the case that a=1 and b=m gives one such factorization. Call this the trivial factorization of m.

Whenever m = ab, setting s = (a+b)/2 and t = (b-a)/2 makes:
s^2 = (a^2+2ab+b^2)/4, and
t^2 = (a^2-2ab+b^2)/4, so that
s^2-t^2 = (s+t)(s-t) = ab = m.

Thus every factorization of m into the product of integers, ab, corresponds to an expression of m as the difference of perfect squares, s^2-t^2. Thus, since m+t^2 = s^2, one can find a factorization of m by trying out successive perfect squares t^2 to add to m until the sum m+t^2 is itself a perfect square, which gives the value of s^2 corresponding to that t^2. This is the essence of
Fermat’s method of factorization, and it is no quicker in finding such values
for an arbitrary m than trial division methods.

Because perfect squares are congruent to either 0 or 1 modulo 4, s and t in any expression of odd positive m = s^2 – t^2 will be even and odd, or odd and even, according to whether m is congruent to 1 or to -1 (or 3) modulo 4, in this way: If m is congruent to -1 modulo 4, then s will always be even and t will always be odd. If m is congruent to 1 modulo 4, then s will always be odd and t will always be even. This is true for any factorization of m into odd positive integers, since the corresponding s, t pair must have m = s^2 – t^2 give the same value modulo 4 (not to mention the same value, m, overall).

When (m+1)/2, which is the s term for the trivial factorization m = m*1, is even, this corresponds to m being congruent to -1 modulo 4. When (m+1)/2 is odd, this corresponds to m being congruent to 1 modulo 4.

SOME DEFINITIONS OF NEW CONCEPTS

Let c^2 be the smallest perfect square greater than a particular odd positive integer m that is even or odd as (m+1)/2 is even or odd. Define this c^2 to be the Ceiling Square of m, and c to be the Ceiling Root of m.

Since m = c^2-r for some nonnegative Remainder r, every odd positive integer m has that unique expression in terms of its Ceiling Square and Remainder.

When a factorization of m gives, as described above, its expression as the difference of two perfect squares, m = s^2-t^2, s will always be at least as large as the ceiling root of m. When the remainder r in m = c^2-r is a perfect square, Fermat’s factorization method gives an immediate answer. Otherwise, consider s-c, the amount to increase c so that the resulting perfect square differs from m by a perfect square, to be the Ascent of the corresponding factorization of m.

Given arbitrary m with Ceiling Root c, produce a series of remainders f(n) as
follows:

f(n) = (c+n)^2-m.

f(0) will be r, and one can refer to f(0), f(1), … as the Remainder Series of
m = c^2-r. A corresponding quadratic polynomial in n gives this series of values as the non-negative integer values of r(n) = n^2+2cn+r. One can thus call this polynomial the Remainder Function of m.

THE ZONE GRID

Define a function on the Cartesian (x,y) plane Z(x,y) = y+x(x+1).

This function’s values at integer points on the Cartesian plane shifted copies
of the integer number line parallel to the y axis. All perfect squares among the non-negative values on these number lines fall along the integer points of the family of lines y = (2n-1)x+n^2 for n = 0, 1, 2, … The integer values of Z(x,y) along these lines are the nonnegative integer perfect squares in ascending sequence as x increases, with different values where they intersect the vertical line x=0. Define the line in this family that passes through (0,n^2) as Zone Boundary n, and call the values of Z(x,y) at the integer points on the Cartesian plane the Zone Grid.

FACTORIZATION IMPLICATIONS OF THE REMAINDER SERIES AND THE ZONE GRID

If one were to take the Remainder Series of a particular positive odd integer m as defined above, and assign it points on the Zone Grid such that one located f(0) on the vertical line x=0, f(1) on x=1, and so on, one would see that the Remainder Series and Remainder Function describes a straight line on the Zone Grid. This line, the Remainder Line for m, will intersect the Zone Boundaries at various points one can calculate using the slope-intercept equation of the Remainder Line. One can derive this easily from the f(0) and f(1) values.

The values of the Remainder Series f(x) for positive integer x which are perfect squares not only correspond to remainders which allow representation of m according to Fermat factorization, but also correspond to the points where the Remainder Line for m intersects one of the Zone Boundaries at an integer point.

These implications do not directly give a formula for computing Ascent given
values of m, c, and r. They however suggest to the author that such a formula
might not be forever out of reach, by which one can factor an arbitrary m=c^2-r given its Remainder Series and its Remainder Line on the Zone Grid.