If odd integer m is a discrete semiprime, then the search for the least positive integer whose square when added to m produces another perfect square is the problem addressed by the admittedly slow process of Fermat’s factorization method.

Despite its lack of advantages over trial division as a factorization method, Fermat’s approach fascinates me and has been central to the past year’s work I have done on finding new and faster factorization methods based on the patterns I have observed.

One such pattern has come to me recently that is striking in its beauty, if not utility: An odd discrete semiprime will have two possible factorizations, which correspond to two distinct expressions of it as the difference between perfect squares. The trivial factorization of discrete semiprime m as being 1 times m corresponds to m’s expression as s^{2}-t^{2} where s=t+1. All odd integers have such an expression as the difference between consecutive perfect squares: When you look at x^{2} for x=0,1,2,… you will see each differs from its predecessor by 1, 3, 5, …, which is, by the way, what one would expect from a quadratic polynomial’s values.

But as I was working on compiling a large table of the discrete semiprimes less than or equal to 20000, in numerical order (it’s a bigger bite than I can chew, I am finding), with their non-trivial and trivial expressions as differences of squares, I came upon the above graph, which is the logarithmic-y-axis representation of the non-trivial solution’s value of t plotted versus the trivial solution’s value of t. But beyond that, I found the following relationship, based on the value of the smaller of the two primes in the factorization of m:

Let m=pq with p>q.

Let t_{1} squared be the nontrivial perfect square added to m to produce a perfect square equal to s_{1} squared. The difference s_{1}-t_{1} will be equal to q.

Let t_{2} squared be the trivial perfect square added to m to produce the perfect square of s_{2}=t_{2}+1. t_{2} as it turns out always equals (m-1)/2.

I assert (without proof, though such might not be difficult) that:

t_{1}=(t_{2}-(q^{2}-1)/2)/q.

Again, I don’t know that it gives much new information – I suspect it doesn’t – but it’s a compact formula behind the properties of a pretty graph.

## Leave a ReplyCancel reply