0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ $809009=823\times983$, so I'm not sure why your professor said 5 values is enough. $\endgroup$ – Kenny Lau May 6 '16 at 18:20
  • 2
    $\begingroup$ $\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. $\endgroup$ – Daniel Fischer May 6 '16 at 18:33
  • 1
    $\begingroup$ @KennyLau Because the midpoint of $823$ and $983$ is $903$, which is very close to $\sqrt{809009}$. $\endgroup$ – Erick Wong May 6 '16 at 18:48
  • $\begingroup$ @DanielFischer: couple starting at $900$ with your observation and $903$ will be the first value tried. $\endgroup$ – Ross Millikan May 6 '16 at 18:58
  • $\begingroup$ @RossMillikan Yes, duh, I completely mis-thought. Forgot that you get $(u+v)\cdot(u-v)$. $\endgroup$ – Daniel Fischer May 6 '16 at 19:00
1
$\begingroup$

$$\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$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.