Integer Factorization: Quick Summary of Last Night’s Simplification “Revelation”


Let m be an odd positive integer we wish to factor. Let c be the smallest integer (also positive) so that c2>m. (If m is a perfect square, we are done.) Set r=c2-m.

The least non-negative value of x for which x2+2cx+r is a perfect square is a value of x which produces s=c+x whose square differs from m by a perfect square amount t2: m=s2-t2=(s+t)(s-t), quite probably a desired factorization. (With hat-tip to Pierre de Fermat.)

Leave a ReplyCancel reply