Difference of two squares Created 2026-09-24 Updated 2026-11-05
The difference of two squares identity is
It follows by expanding the right side and cancelling its cross terms. It holds for real numbers and, more generally, in a commutative ring.
For integers , the factors and have the same parity. Conversely, any integer factorization with factors of the same parity yields and . Thus an integer is a difference of two squares exactly when it is not congruent to two modulo four: odd values use , and multiples of four use . This is the factor-pair interpretation behind Fermat's factorization method.
Fermat's factorization method Created 2026-10-14 Updated 2026-11-05
For a positive odd integer , Fermat's factorization method searches for integers satisfying . Start at and test successive values until is a perfect square . The difference of two squares then gives . For an even input, remove factors of two first.
For example, starts at . The differences and fail the perfect square test, whereas . Hence .
The search always reaches at least the trivial factor pair , at . It is useful when a nontrivial factor pair is close: that pair is reached at , with
A small difference between factor sizes therefore requires few trials. This is a different advantage from looking for a small prime factor by trial division.
Write with odd. If , the polynomial factor of by , evaluated at , supplies a proper divisor. Therefore must be a power of two. Conversely this is only a necessary condition for primality testing.
For a prime factor of the number, is odd and does not divide . Its multiplicative order satisfies but , since . When is a power of two, every proper divisor of divides , so . By Lagrange theorem in the multiplicative group of a finite field, . Thus .
The Fermat factorization method searches for a difference of two squares: starting at , increase until , and return . Every factorization of an odd integer has this form, with and . For , the successive differences at are . The last is , giving . Trial division by the primes up to their respective square roots confirms that both factors are prime.
Write with . The difference of two squares factors as
The final factor is an integer, so divides the difference. By congruence modulo an integer, .