# Square root of prime numbers

I found that the square root of any prime number S can be approximated, at the n-th order, as a rational number represented by the polynomials shown below. $$x_0$$ is an initial seed, which is a rational number chosen “close” to $$\sqrt S$$. I used the iterative method, not the continued fractions

My question: Is someone aware of this result? Is it already known and has been published elsewhere? If affirmative, please post the reference!

• Someone might already be aware of the result if there was a natural way how this result would come up, or if the result somehow had "practical" significance. Maybe it would help to add some context why the given formula is special or useful, and how you derived it.
– TMM
May 5 at 16:13
• Surely this works for any number $S$, not just prime numbers? Could it be a version of Newton's method? May 5 at 18:28
• If you call $F_n(t) = (x_0+t \sqrt{S}) ^n$, it seems like both the numerator and the denominator can be expressed in terms of $F_n$ and its antiderivative in $\pm 1$. Is this the way you found the formula? May 5 at 21:01
• @Andrea, what does "its antiderivative in $\pm1$" mean? May 5 at 23:53
• For antiderivative I mean $G_n(t)=\frac{(x_0+t\sqrt{S}) ^{n+1}}{\sqrt{S}(n+1)}$. This has the property that $G_n'(t) =F_n(t)$. It seems like you can express the numerator as something like $F_{2^n}(1) +F_{2^n}(-1)$ and the denominator as $G_{2^n}(1) +G_{2^n}(-1)$. May 6 at 9:06

My impression is that you have developed $$(x_0-\sqrt{S})^{2^n}$$ with Newton binomial formula, separated the terms with even index from the terms with odd index to get an expression of the form $$A_n-\sqrt{S}B_n$$ to approach $$\sqrt{S}$$ by $$A_n/B_n$$.
More precisely, you have $$A_n = \frac{(x_0+\sqrt{S})^{2^n}+ (x_0-\sqrt{S})^{2^n}}{2}$$ and $$B_n = \frac{(x_0+\sqrt{S})^{2^n}-(x_0-\sqrt{S})^{2^n}}{2\sqrt{S}}.$$
The successive approximations you get are the same as approximations provided by Newton method applied to the function $$f : x \mapsto x^2-s$$. Indeed, $$A_0/B_0=x_0$$ and for every $$n \ge 0$$, $$\frac{A_n}{B_n} - \frac{f(A_n/B_n)}{f'(A_n/B_n)} = \frac{A_n}{B_n} - \frac{A_n^2/B_n^2 - s}{2A_n/B_n} = \frac{A_n^2+sB_n^2}{2A_nB_n} = \frac{A_{n+1}}{B_{n+1}},$$ since $$4(A_n^2+sB_n^2) = 2A_{n+1}$$ and $$4A_nB_n = 2B_{n+1}$$.