A Method of Construction and a Theorem for Integer Factorization

Advertisements

By J. Calvin Smith, B.A., Mathematics, Georgia College, Milledgeville, Georgia, United States of America (1979) – Retired Member, American Mathematical Society

Written 14 March 2023 at Mountain River Chalet (the author’s home), Talking Rock, Georgia, USA.

The following definitions, theorem, and construction are the end result of research by the author into factorization of odd positive integers.

Let m be a positive odd integer for which we desire factorization. Let c be either the least integer greater than or equal to the square root of m, or that quantity plus one, whichever of these is odd or even as (m+1)/2 is odd or even. c2 will then be the least respectively odd or even perfect square greater than m. Call c2 the Ceiling Square of m. When m=c2-r for some positive r, r is the Remainder in what follows.

Preliminary results: Every expression of m as the product of two odd integers m=ab, with a<b, will correspond one-to-one to an expression as the difference of two perfect squares m=s2-t2, where s=(a+b)/2 and t=(b-a)/2. Furthermore, the Ceiling Square as defined above will be even or odd as s2 is even or odd, with t2 being odd or even accordingly. This follows easily as a consequence of the possible values of perfect squares modulo 4.

This associates factorization of odd positive integers with finding the least perfect square that, when added to m, produces a perfect square sum.

These ideas, and some constructions using number grids and analytic geometry principles, led the author to the following construction and theorem:

Given m=c2-r derived as above, construct the following equation for what we shall call the Remainder Line in the Cartesian Plane:

y = [2(c-x0)-1]x + r+x02-x0c,

where x0 is the integer ceiling of the square root of r.

Construct equations for a family of lines, which we shall call Zone Lines, as follows:

yn=(2n-1)x+n2.

Calculate the series of rational numbers which are the intersection points between the Remainder Line and the Zone Lines numbered 0, 1, 2, and so on, until 2n-1 exceeds the slope of the Remainder Line.

Theorem: The least non-negative value of n for which the intersection point calculated above has an integer x value, referred to here as xint, will lead to a factorization of m as follows: Let s=c+xint-x0, with c and x0 being the square root of the Ceiling Square and the integer ceiling of the square root of r, as defined above. s2-m will be a perfect square t2, so that m=(s+t)(s-t). In the case that m is prime, s will equal t+1; otherwise, this will be a factorization of the composite m.

Author’s Note: If one observes the intersection points of the Remainder Line with the Zone Lines, one will see the series of x values can be expressed as rational numbers whose numerator increases quadratically while the denominator decreases linearly. This may give further insight into factorization by determining formulaically which Zone’s values will give integer results.

9 responses to “A Method of Construction and a Theorem for Integer Factorization”

  1. […] whose diagonal one would form on the Zone Grid by drawing the remainder line calculated by the previously explained construction method, from a zone boundary that passes through the greatest perfect square less than what I have been […]

  2. […] square greater than or equal to m that is odd or even as (m+1)/2 is odd or even, and r=c2-m, we can construct a Zone Grid and compute the slope of a Remainder Line passing through appropriately chosen values of r0=r and […]

  3. […] Lines on the Zone Grid. I established the construction of such a grid and the lines in question in a post a few weeks ago, and now I’m posting to give you an update. I’ve not found anything yet that gives me further […]

  4. […] So here we go, jumping right into it. For recent background, see here. […]

  5. […] in the series after that is also divisible by n. Further, the Characteristic Line on the Zone Grid (see here for my construction of this concept) has slope and y-intercept values that change linearly, albeit at different rates, as c increases […]

  6. […] go to the Zone Grid as defined here. Position it so that the x axis points straight down and the y axis points to the right. The shifted […]

  7. […] start with the Zone Grid, whose concept I posted here, and whose behaviors in connection with a Characteristic Polynomial and Characteristic Line, both […]

  8. […] First of all, I want to write down on my blog some of the nitty gritty, in a fashion I hope will be clear, of how I construct and use the Zone Grid I have been using in my calculations and explorations, and my discovery of how to plot thereon the Remainder Line corresponding to the Characteristic Polynomial f(x)=x2+2cx+r for a positive odd integer m where c is the Ceiling Root and r the Remainder of m so that m=c2-r constrained by the rules of construction I briefly albeit inadequately described here. […]

Leave a ReplyCancel reply