Some Number Theory


Let prime number p be a factor of positive integer m. The integer m has an expression as the difference between two perfect squares s and t, with s greater than t, such that either s+t or s-t equals p. When m=p×1, this will be the only such s and t, and s=t+1.

Define the ceiling square of a positive number as the smallest perfect square greater than or equal to the number. The only primes for which s in the above relationship is the square root of p’s ceiling square are 3 and 5. (N.B.: These are the only numbers with a cyan background in the “integer triangle” depicted in my previous post.)

EDITED TO ADD: Also, I have a follow-up questions to these observations, for anyone who is interested: Does this transform the factorization of an integer m=pq, p<q, into the process of finding s and t such that s2-t2=m and s-t=p? I think it does, but I also expect it doesn’t simplify anything. I have shared this question on Twitter already, tagging the American Mathematical Society account there. My hopeful (perhaps unreasonably so) heart says it’s worth a shot.

One response to “Some Number Theory”

  1. […] Someone with experience in running advanced algorithms for integer factorization, such as the Number Field Sieve, could if they wished compare the performance of this short script to such methods. This algorithm works to factor an integer m=pq especially rapidly when the factors are somewhat but not necessarily especially close to the square root of m. The basic realization that led me to write this code occurred very early this morning and I described it briefly in my blog post here, “Some Number Theory.” […]

Leave a ReplyCancel reply