Associated Topics || Dr. Math Home || Search Dr. Math

### Fermat's Factorization Method

```
Date: 01/29/99 at 15:22:57
From: Karthick
Subject: Number theory, Fermat's factorisation methord.

I remember reading somewhere that Fermat devised a rule for
factorising that works well if the factors are close. You take the
integer part of the square root of the number to be factorised, form a
series with it, and continue until some term becomes an integer.

All this happened when I was trying to factorise 99899. Can you help
me with this? And provide the general method as well?

```

```
Date: 01/29/99 at 17:04:59
From: Doctor Rob
Subject: Re: Number theory, Fermat's factorisation methord.

Thanks for writing to Ask Dr. Math!

You remember Fermat's Method well as far as you got. To factor N, start
with the next integer a0 not smaller than its square root. Square that
and subtract N, to give a0^2 - N. Take the square root of that number
to give sqrt(a0^2-N). Since a0 >= sqrt(N), this is a real number.

If it is an integer b, then

a0^2 - N = b^2, and
N = a0^2 - b^2 = (a0-b)*(a0+b),

and you have factored the number N.

If it is not an integer, replace a0 by a1 = a0 + 1. That increases
a0^2 - N by 2*a0 + 1 to give a1^2 - N. Again take the square root, and
see if you get an integer b. If not, increase a1^2 - N by 2*a1 + 1, and
take the square root again. Continue this until you have factored N, or
until sqrt(ai^2-N) exceeds N/2.

As an example, let's factor N = 1037.

i    ai   ai^2-N   2*ai+1   sqrt(ai^2-N)
-----------------------------------------
0    33       52     67       7.2111
1    34      119     69      10.9087
2    35      188     71      13.7113
3    36      259     73      16.0935
4    37      332     75      18.2209
5    38      407     77      20.1742
6    39      484     79      22.0000 = 22 = b

and so 1037 = (39-22)*(39+22) = 17*61.

Now you do N = 99899, with a0 = 317.

- Doctor Rob, The Math Forum
http://mathforum.org/dr.math/
```
Associated Topics:
High School Number Theory
Middle School Factoring Numbers

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search