# Use Fermat factorization to factor $809009\ldots$

Use Fermat factorization to factor $809009\ldots$

So far I have:

\begin{align} \sqrt{809009} & = 889.449 \\ & = 890 \\[6pt] \sqrt{890^2 - 809009} & = 130\ldots ∉ \mathbb Z \\[6pt] \sqrt{891^2 - 809009} & = 122\ldots ∉ \mathbb Z \\[6pt] & \,\,\,\vdots \\[6pt] \sqrt{899^2 - 809009} & = 28\ldots ∉ \mathbb Z \end{align}

Ideally should equate to a whole number at some point, and according to my professor I shouldn't have to try for more than about 5 values. Not sure if I made an arithmetic mistake or just not using the formula correctly. Any help is appreciated.

• $809009=823\times983$, so I'm not sure why your professor said 5 values is enough. – Kenny Lau May 6 '16 at 18:20
• $\sqrt{809009} \approx 899.449$, you're starting early. Congruence considerations show that $m^2 - 809009$ can only be a square if $m \equiv 3,5,7 \pmod{10}$. That doesn't take you to trying only about five values, though. – Daniel Fischer May 6 '16 at 18:33
• @KennyLau Because the midpoint of $823$ and $983$ is $903$, which is very close to $\sqrt{809009}$. – Erick Wong May 6 '16 at 18:48
• @DanielFischer: couple starting at $900$ with your observation and $903$ will be the first value tried. – Ross Millikan May 6 '16 at 18:58
• @RossMillikan Yes, duh, I completely mis-thought. Forgot that you get $(u+v)\cdot(u-v)$. – Daniel Fischer May 6 '16 at 19:00

## 1 Answer

$$\sqrt{809009}=899.449$$

Your teacher is right. You can get it in about 5 values.

You should start from 900 rather than 890.

I have written some Python code to avoid doing manual work.

http://www.codeskulptor.org/#user41_l8aZFH9i8fjEuMO.py

$$\sqrt{903^2-809009}=80$$

Hence the factors are $903-80=823$ and $903+80=983$