Fermat's factorization method: Difference between revisions

Revision as of 23:17, 18 June 2024

Revision as of 23:19, 18 June 2024

Line 41:

|}

The third try produces the perfect square of 441. SoThus, <math>a = 80</math>, <math>b = 21</math>, and the factors of {{math|5959}} are <math>a - b = 59</math> and <math>a + b = 101</math>.

Suppose N has more than two prime factors. That procedure first finds the factorization with the least values of ''a'' and ''b''. That is, <math>a + b</math> is the smallest factor ≥ the square-root of ''N'', and so <math>a - b = N/(a + b)</math> is the largest factor ≤ root-''N''. If the procedure finds <math>N=1 \cdot N</math>, that shows that ''N'' is prime.