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.


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.


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

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.


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.


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.

Leave a ReplyCancel reply